我想知道 C++ 中 make_heap 的算法是什么，使得复杂度为 3*N？我能想到的通过插入元素来创建堆的唯一方法具有 O(N Log N) 的复杂性。非常感谢！
问问题
6188 次
1 回答
22
您将堆表示为数组。'th元素下面的两个元素i在位置2*i+1和2*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 回答