java - 通过插入实现构建堆功能

Question

你能告诉我这两个用于构建堆的伪代码是否总是返回相同的堆？这是“经典”众所周知的 BuildHeap 代码：

BuildHeap(A) // A 是一个未排序的数组

for(i = A.size/2 down to 1) do 
    MaxHeapify(A,i) 

这是使用插入代码构建堆：

Build-Max-Heap-By-Insertion(A)

heapsize[A] = 1
for i=2 to length[A]
    Max-Heap-Insert(A,A[i])

谢谢！

Answer 1

看起来好像您指的是从头开始构建堆的线性时间方法，并将其与迭代地构建堆进行比较，一次接受一个项目，每次插入后堆不变量为真。这两个——假设你得到了所有的细节——都将通过构建一个堆来完成。

在第一种情况下，请注意，如果数组已经满足堆不变量，则不会更改。这意味着任何排列对象的方式构成有效堆都不会改变。由于可能有不止一种这样的安排 - 特别是如果有相同比较的键 - 不能保证您最终得到的特定安排将匹配从相同项目创建有效堆的任何其他方式。