我想知道 C++ 中 make_heap 的算法是什么，复杂度为 3*N？我能想到的唯一方法是通过插入复杂度为 O(N Log N) 的元素来创建堆。非常感谢!
最佳答案
您将堆表示为一个数组。 i 元素下方的两个元素位于 2*i+1 和 2*i+2 位置。如果数组有 n 个元素，那么从末尾开始，取出每个元素，让它“落”到堆中的正确位置。这是要运行的 O(n)。
为什么？那么对于元素的 n/2 来说，没有子元素。对于 n/4 有一个高度为 1 的子树。对于 n/8 有一个高度为 2 的子树。对于 n/16 有一个高度为 3 的子树。等等。所以我们得到了系列 n/2 + 2*n/2 + 3*n/2 + ... = (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 = n 。所以“看看我是否需要再跌一次，如果需要，我会跌倒哪个方向？比较结果是 n 。但是你从离散化中得到了四舍五入，所以你总是得出少于 n 套交换找出来。每个最多需要3次比较。(将根与每个 child 进行比较，看是否需要下降，如果根比两个 child 都大，则将 child 相互比较。)
关于c++ - C++ 中的 make_heap 如何实现复杂度为 3N？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5057562/