如何在不遞歸的情況下編寫Max Heap代碼

我從算法書的介紹中編寫了MAX-HEAPIFY（A，i）方法。現在我想用while循環不遞歸地編寫它。你能幫我嗎？如何在不遞歸的情況下編寫Max Heap代碼

2014-10-10 Parisa

發佈您的遞歸版本。 – 2014-10-10 07:53:37

你可以使用while循環條件你的我< = HEAPSIZE和使用所有其他相同的條件，除非你找到正確的位置只是打破循環。代碼： -

while (i < = heapsize) { 
le <- left(i) 
ri <- right(i) 
if (le<=heapsize) and (A[le]>A[i]) 
    largest <- le 
else 
    largest <- i 
if (ri<=heapsize) and (A[ri]>A[largest]) 
    largest <- ri 
if (largest != i) 
{ 
    exchange A[i] <-> A[largest] 
    i <- largest 
} 
else 
    break 
}

來源

2014-10-10 10:00:59 aurilio

你爲什麼使用其他的，並在最後一行？ – Parisa 2014-10-10 13:45:54

要檢查邊界條件 - 如果元素位於正確的位置，則不應再執行heapify並從循環中出來。 – aurilio 2014-10-13 07:17:07

我想如果我們把「我 smasher 2017-09-15 06:42:58

上述工程的解決方案，但我認爲下面的代碼是接近遞歸版本

(* Code TP compatible *) 
const maxDim = 1000; 
type TElem = integer; 
    TArray = array[1..maxDim]of TElem 

procedure heapify(var A:TArray;i,heapsize:integer); 
var l,r,largest,save:integer; 
    temp:TElem; 
(*i - index of node that violates heap property 
    l - index of left child of node with index i 
    r - index of right child of node with index i 
    largest - index of largest element of the triplet (i,l,r) 
    save - auxiliary variable to save the value of i 
    temp - auxiliary variable used for swapping *) 
begin 
    repeat 
    l:=2*i; 
    r:=2*i + 1; 
    if(l <= heapsize) and (A[l] > A[i]) then 
     largest:=l 
    else 
     largest:=i; 
    if(r <= heapsize) and (A[r] > A[largest]) then 
     largest:=r; 
    (*Now we save the value i to check properly the termination 
    condition of repeat until loop 
    The value of i will be modified soon in the if statement *) 
    save:=i; 
    if largest <> i then 
    begin 
     temp:=A[i]; 
     A[i]:=A[largest]; 
     A[largest]:=temp; 
     i:=largest; 
    end; 
    until largest = save; 
    (*Why i used repeat until istead of while ? 
    because body of the called procedure will be executed 
    at least once *) 
end;

還有一件事，在Wirth的算法+數據結構=程序
可找到沒有遞歸的篩選程序
但我們應該引入布爾變量或break來消除goto語句

來源

2018-03-03 06:03:52

如何在不遞歸的情況下編寫Max Heap代碼

回答

相關問題