arrays - 通过数组实现二叉堆

Question

我不想通过给定的数组创建二进制最大堆。我可以通过两种方式实现它：
1.制作整个数组的堆，然后通过叶子节点开始堆到顶部。
2.将一个元素从数组中一个一个地插入到堆中，同时堆化。

这两种方法都给了我一个最大堆，但彼此不同。那么哪种方法是正确的呢？

Answer 1

您可以以任何一种方式实现堆，并且两者都是正确的，因为它们遵守堆排序的基本规则，即父键必须大于任何一个子节点。尽管它们可能会导致不同的堆。

Method-1- 将整个数组堆成一个堆，然后通过叶子节点开始堆到顶部。通过这种方法，构建堆的比较次数为 O(N)，即它需要线性比较次数，因此需要线性时间。

Method-2- 将一个元素从数组中一个一个地插入到堆中，同时堆化。将元素插入有序堆平均需要 logN 次比较。因此，同时插入 N 个项目和堆排序需要 log1 + 2log2 +3log3 + ... + NlogN ~ NlogN 比较，因此需要线性时间。

因此，方法一更可取，因为它需要更少的比较次数，因此时间更短。

Answer 2

看起来两者是不同的：
1.当您一个接一个插入时：基本上您是在插入已经是堆的二叉树并调用 heapify
2.当您一次将所有内容插入一个数组然后将其完全堆起来时没有使用 heapify（BuildHeap 函数）。因为那还不是一个堆。

当您插入已经是堆的数组时使用 Heapify

读这个。