堆结构

堆的主要操作:

*建立一个堆
*往堆里添加新元素
*访问最大/最小值
*删除最大/最小值

模板如下:

#include<cstdio>
#define MAX_SIZE 100
int A[MAX_SIZE]={0,1,2,3,4,5,6,7,8,9},N=9; //下标从1开始 

void downAdjustment(int A[],int idx);//向下调整 
void buildHeap(){
    int i;
    for(int i=N/2;i>=1;i--)
        downAdjustment(A,i);
} 

void downAdjustment(int A[],int idx){
    int leftChild= 2*idx;
    int rightChild= 2*idx+1;
    int max;
    if(leftChild > N)   return;
    if( rightChild >N||(A[leftChild] > A[rightChild]) )
        max=leftChild;
    else
        max=rightChild;

    if(A[idx] < A[max]){
        int tmp=A[idx];
        A[idx]= A[max];
        A[max]=tmp;
        downAdjustment(A,max);//递归向下调整 
    } 
}

//向上调整 
void upAdjustment(int A[],int idx){
    int parent= idx/2;
    if(parent < 1) return;

    if(A[idx] > A[parent]){
        int tmp=A[idx];
        A[idx]=A[parent];
        A[parent]=tmp; 
        upAdjustment(A,parent);//递归向上调整 
    }
}

//添加新元素 
void addAElement(int ele){
    A[++N] = ele;
    upAdjustment(A,N);
}

//访问最大值 
int maxElement(){
    return A[1]; 
} 


//删除最大值 
void deleteMax(){
    A[1]=A[N];
    N--;
    downAdjustment(A,1);
}

int main(){
    buildHeap();    
    for(int i=1;i<=N;i++)
        printf("%d ",A[i]);

    printf("\n--------\n\n");
    addAElement(10);
    for(int i=1;i<=N;i++)
        printf("%d ",A[i]);
    deleteMax();
    printf("\n---\n\n");
    for(int i=1;i<=N;i++)
        printf("%d ",A[i]);

    return 0;
}