通過插入實現構建堆函數

Question

請問能否告訴我這兩個用於構建堆的僞代碼是否總能返回相同的堆？ 這是 「經典」 的公知的BuildHeap代碼：

BuildHeap（A） // A是一個未排序的陣列

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

這是一個堆的與插入碼建築物：

內建最大堆-BY-插入（A）

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

謝謝！

Answer 1

看起來好像您指的是從頭開始構建堆的線性時間方式，並將其與迭代地構建堆進行比較，一次接受一個項目，並且在每次插入後堆恆定不變。這兩種方法 - 假設你完全掌握了所有的細節 - 將會通過構建一堆東西來完成。

在第一種情況下，請注意，如果數組已經滿足堆不變量，則不會更改。這意味着任何安排相當於一個有效堆的對象的方式都不會改變。由於可能有多個這樣的安排 - 特別是如果有相同比較的密鑰 - 不能保證您最終的特定安排將與從相同項目創建有效堆的任何其他方式相匹配。