data-structures - 如何在没有递归的情况下编写 Max Heap 代码

Question

我已经从算法介绍书中编写了 MAX-HEAPIFY(A,i) 方法。现在我想用while循环编写它而不用递归。你能帮我吗？

Answer 1

您可以使用带有 i <= HEAPSIZE 条件的 while 循环并使用所有其他相同的条件，除非您找到正确的位置只是打破循环。代码：-

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
}             

Answer 2

上面的解决方案有效，但我认为以下代码更接近递归版本

(* 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 的算法 + 数据结构 = 程序
中可以找到没有递归的 sift 过程，
但我们应该引入布尔变量或中断来消除 goto 语句