1 #include <iostream>  2 #include <fstream>  3 #include <cstring>  4 #include <vector>  5 #include <queue>  6 #include <stack>  7 #include <algorithm>  8 #include <cmath>  9  10 using namespace std; 11  12 #define loop(i,n) for(int i=0;i<(n);i++) 13 #define loop2(i,n) for(int i=1;i<=(n);i++) 14  15 const int maxn=101; 16 int inf=99999999; 17  18 int h[maxn]; //用来存放堆的数组 19 int n; //用来存储堆中元素的个数，也就是堆的大小 20 //交换函数，用来交换堆中的两个元素的值 21 void swap(int x,int y) 22 { 23   int t; 24   t=h[x]; 25   h[x]=h[y]; 26   h[y]=t; 27 } 28  29 void siftdown(int i)  //传入一个需要向下调整的结点编号i，这里传入1，即从w堆的顶点开始向下调整 30 { 31   int t,flag=0; //flag用来标记是否需要继续向下调整 32  33   while(i*2<=n && flag==0) //当i结点有儿子（其实是至少有左儿子的情况下）并且有需要继续调整的时候，循环就执行 34   { 35     if(h[i]>h[i*2]) //首先判断它和左儿子的关系，并用t记录值较小的结点编号 36       t=i*2; 37     else 38       t=i; 39     if(i*2+1<=n) //如果有右儿子的值更小，更新较小的结点编号 40       if(h[t]>h[i*2+1]) 41         t=i*2+1; 42     if(t!=i) //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的 43     { 44       swap(t,i); //交换它们，注意swap函数需要自己来写 45       i=t; //更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整 46     } 47     else 48       flag=1;//否则说明当前的父结点已经比两个子结点都要小了，不需要再进行调整了 49   } 50 } 51  52 void siftup(int i) //传入一个需要向上调整的结点编号i 53 { 54   int flag=0; //用来标记是否需要继续向上调整 55   if(i==1)return;//如果是堆顶，就返回，不需要调整了 56  57   while(i!=1 && flag==0)//不在堆顶，并且当前结点i的值比父结点小的时候就继续向上调整 58   { 59     if(h[i]<h[i/2]) //判断是否比父结点的小 60       swap(i,i/2); //交换它和它爸爸的位置 61     else 62       flag=1; //表示已经不需要调整了，当前结点的值比父结点的值要大 63     i=i/2; //这句话很重要，更新编号i为它父结点的编号，从而便于下一次继续向上调整 64   } 65 } 66 //删除最大的元素 67 int deletemax() 68 { 69   int t; 70   t=h[1];//用一个临时变量记录堆顶点的值 71   h[1]=h[n];//将堆的最后一个点赋值到堆顶 72   n--;//堆元素减少1 73   siftdown(1); //向下调整 74   return t;  //返回之前记录的堆的顶点的最大值 75 } 76  77 void create() 78 {   79   for(int i=n/2;i>=1;i--) 80     siftdown(i); 81 } 82  83 void heapsort() 84 { 85   while(n>1) 86   { 87     swap(1,n); 88     n--; 89     siftdown(1); 90   } 91 } 92  93  94 void test() 95 {    96   freopen("minheap.in","r",stdin);   97   //freopen("minheap.out","w",stdout);  98   int num; 99   cin>>num;100   for(int i=1;i<=num;i++)101     cin>>h[i];102   n=num;103 104   create();105   //heapsort();106   //删除顶部元素，连续删除n次，其实也就是从大到小把数输出来107   for(int i=1;i<=num;i++)108     cout<<deletemax()<<" ";109 110   cout<<endl;111 }112 113 int main () 114 {        115     test();        116     return 0;117 }

1499 5 36 7 22 17 46 12 2 19 25 28 1 92