14

我想知道 C++ 中 make_heap 的算法是什么,使得复杂度为 3*N?我能想到的通过插入元素来创建堆的唯一方法具有 O(N Log N) 的复杂性。非常感谢!

4

1 回答 1

22

您将堆表示为数组。'th元素下面的两个元素i在位置2*i+12*i+2。如果数组有n元素,那么从末尾开始,取出每个元素,让它“落”到堆中的正确位置。这是O(n)要跑的。

为什么?元素n/2中没有子元素。因为n/4有一棵高度为 1 的子树。因为n/8有一棵高度为 2 的子树。对于n/16一棵高度为 3 的子树。依此类推。所以我们得到了系列。所以“看看我是否需要再跌一次,如果是的话,我会跌到哪条路?比较的总数。但是你从离散化中得到四舍五入,所以你总是得出少于一组交换来计算out. 每个最多需要 3 次比较。(比较 root 到每个孩子看它是否需要下降,如果 root 比两个孩子都大,那么孩子相互比较。)n/22 + 2*n/23 + 3*n/24 + ... = (n/2)(1 * (1/2 + 1/4 + 1/8 + . ...) + (1/2) * (1/2 + 1/4 + 1/8 + . ...) + (1/4) * (1/2 + 1/4 + 1/8 + . ...) + ...) = (n/2) * (1 * 1 + (1/2) * 1 + (1/4) * 1 + ...) = (n/2) * 2 = nnn

于 2011-02-20T14:42:21.093 回答