如何在不递归的情况下编写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代码

回答

相关问题