算法导论 6.25

 题目：MAX-HEAPIFY的代码效率较高，但第10行中的递归调用可能例外，它可能使某些编译程序产生低效的代码。请用迭代的控制结构（循环）取代递归结构，从而写一个更为高效的MAX-HEAPIFY。

代码：

#include "iostream"
using namespace std;

int LEFT(int i){
    return 2*i+1;
}

int RIGHT(int i){
    return 2*i+2;
}

void MAX_HEAPIFY(int A[],int i){
    int l,r,largest;
    int t;
    while((l=LEFT(i))<10){
        if(A[l]>A[i])
            largest=l;
        else 
            largest=i;
        if((r=RIGHT(i))<10&&A[r]>A[largest])
            largest=r;
        if(largest==i) break; 
        t=A[i];
        A[i]=A[largest];
        A[largest]=t;
        i=largest;
    }
}

void display(int a[]){
    for(int i=0;i<10;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

void main(){
    int a[10]={16,4,10,14,7,9,3,2,8,1};
    display(a);
    MAX_HEAPIFY(a,1);
    display(a);
    getchar();
    getchar();
}