堆的建立、调整、删除、插入

模板：

#include <stdio.h>
#include <algorithm>

#define LEN 10000

using namespace std;

int heap[LEN];    //本例为小根堆 
int n=0;

void downAdjust(int a,int b){    //[a,b]为欲调整的区间 
    int i=a;    //父节点 
    int j=i*2;    //左叶子节点
    while(i<=b){
        if(j+1<=n && heap[j+1]<heap[j]){//在右叶子结点存在的情况下，如果右叶子节点更加小 
            j++;
        }
        if(j<=n && heap[j]<heap[i]){
            swap(heap[i],heap[j]);
            i=j;    //新的循环 
            j*=2;
        }else    //调整完毕，所有叶子都比根节点大 
            break; 
    }
}

void build(){
    for(int i=n/2;i>=1;i--){//n/2 是最后一个节点的父节点。从最后一层开始调整 
        downAdjust(i,n);
    }
}

void pop(){
    heap[1]=heap[n--];
    downAdjust(1,n);
}

void upAdjust(int a,int b){
    int i=b,j=i/2;
    while(j>=a){
        if(heap[j]>heap[i]){
            swap(heap[j],heap[i]);
            i=j;
            j=i/2;
        }else
            break;
    }
}

void push(int elem){
    heap[++n]=elem;
    upAdjust(1,n);
}

void display(){
    for(int i=1;i<=n;i++){
        printf("%d ",heap[i]);
    }
    puts("");
}

int main(){
    freopen("heap.txt","r",stdin);
    int num;
    while(~scanf("%d",&num)){
        heap[++n]=num;
    }
    build();
    //push演示
    puts("push演示");
    push(-1);
    display();
    //堆排序演示 
    puts("堆排序演示");
    while(n>0){
        printf("%d
",heap[1]);
        display();
        puts("");
        pop();
    }

    return 0;
}

测试效果：