1 void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整  2 { 3     int t,flag=0;//flag用来标记是否需要继续向下调整 4     //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行 5     while( i*2<=n && flag==0 ) 6     {        7         //首先判断他和他左儿子的关系，并用t记录值较小的结点编号 8         if( h[ i] > h[ i*2] ) 9             t=i*2;10         else11             t=i;12         //如果他有右儿子的情况下，再对右儿子进行讨论13         if(i*2+1 <= n)14         {15             //如果右儿子的值更小，更新较小的结点编号 16             if(h[ t] > h[ i*2+1])17                 t=i*2+1;18         }19         //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的 20         if(t!=i)21         {22             swap(t,i);//交换它们，注意swap函数需要自己来写23             i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整24         }25         else26             flag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了27     }28 }

 1 void siftup(int i) //传入一个需要向上调整的结点编号i 2 { 3     int flag=0; //用来标记是否需要继续向上调整 4     if(i==1)  return; //如果是堆顶，就返回，不需要调整了    5     //不在堆顶 并且 当前结点i的值比父结点小的时候继续向上调整 6     while(i!=1 && flag==0) 7     { 8         //判断是否比父结点的小 9         if(h[ i]<h[ i/2])10             swap(i,i/2);//交换他和他爸爸的位置11         else12             flag=1;//表示已经不需要调整了，当前结点的值比父结点的值要大13         i=i/2; //这句话很重要，更新编号i为它父结点的编号，从而便于下一次继续向上调整 14     }15 }

 1 #include <stdio.h> 2 int h[ 101];//用来存放堆的数组 3 int n;//用来存储堆中元素的个数，也就是堆的大小 4  5  6 //交换函数，用来交换堆中的两个元素的值 7 void swap(int x,int y) 8 { 9     int t;10     t=h[ x];11     h[ x]=h[ y];12     h[ y]=t;13 }14 15 16 //向下调整函数17 void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整18 {19     int t,flag=0;//flag用来标记是否需要继续向下调整20     //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行21     while( i*2<=n && flag==0 )22     {        23         //首先判断他和他左儿子的关系，并用t记录值较小的结点编号24         if( h[ i] > h[ i*2] )25             t=i*2;26         else27             t=i;28         //如果他有右儿子的情况下，再对右儿子进行讨论29         if(i*2+1 <= n)30         {31             //如果右儿子的值更小，更新较小的结点编号  32             if(h[ t] > h[ i*2+1])33                 t=i*2+1;34         }35         //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的  36         if(t!=i)37         {38             swap(t,i);//交换它们，注意swap函数需要自己来写39             i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整40         }41         else42             flag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了43     }44 }45 46 47 //建立堆的函数48 void creat()49 {50     int i;51     //从最后一个非叶结点到第1个结点依次进行向上调整52     for(i=n/2;i>=1;i--)53     {54         siftdown(i);55     }  56 }57 58 59 //删除最大的元素60 int deletemax()61 {62     int t;63     t=h[ 1];//用一个临时变量记录堆顶点的值64     h[ 1]=h[ n];//将堆得最后一个点赋值到堆顶65     n--;//堆的元素减少166     siftdown(1);//向下调整67     return t;//返回之前记录的堆得顶点的最大值68 }69 70 71 int main()72 {73     int i,num;74     //读入数的个数75     scanf("%d",&num);76 77 78     for(i=1;i<=num;i++)79         scanf("%d",&h[ i]);80     n=num;   81 82     //建堆83     creat();84 85     //删除顶部元素，连续删除n次，其实夜就是从大到小把数输出来86     for(i=1;i<=num;i++)87         printf("%d ",deletemax());88     getchar();89     getchar();90     return 0;91 }

 1 #include <stdio.h> 2 int h[ 101];//用来存放堆的数组 3 int n;//用来存储堆中元素的个数，也就是堆的大小 4  5  6 //交换函数，用来交换堆中的两个元素的值 7 void swap(int x,int y) 8 { 9     int t;10     t=h[ x];11     h[ x]=h[ y];12     h[ y]=t;13 }14 15 16 //向下调整函数17 void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整18 {19     int t,flag=0;//flag用来标记是否需要继续向下调整20     //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行21     while( i*2<=n && flag==0 )22     {        23         //首先判断他和他左儿子的关系，并用t记录值较大的结点编号24         if( h[ i] < h[ i*2] )25             t=i*2;26         else27             t=i;28         //如果他有右儿子的情况下，再对右儿子进行讨论29         if(i*2+1 <= n)30         {31             //如果右儿子的值更大，更新较小的结点编号  32             if(h[ t] < h[ i*2+1])33                 t=i*2+1;34         }35         //如果发现最大的结点编号不是自己，说明子结点中有比父结点更大的  36         if(t!=i)37         {38             swap(t,i);//交换它们，注意swap函数需要自己来写39             i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整40         }41         else42             flag=1;//则否说明当前的父结点已经比两个子结点都要大了，不需要在进行调整了43     }44 }45 46 47 //建立堆的函数48 void creat()49 {50     int i;51     //从最后一个非叶结点到第1个结点依次进行向上调整52     for(i=n/2;i>=1;i--)53     {54         siftdown(i);55     }  56 }57 58 59 //堆排序60 void heapsort()61 {62         while(n>1)63     {64                 swap(1,n);65         n--;66         siftdown(1);67     }68 }69 70 71 int main()72 {73     int i,num;74     //读入n个数75     scanf("%d",&num);76 77 78     for(i=1;i<=num;i++)79         scanf("%d",&h[ i]);80     n=num;   81 82 83     //建堆84     creat();85 86 87     //堆排序88     heapsort();89 90 91     //输出92     for(i=1;i<=num;i++)93         printf("%d ",h[ i]);94 95 96     getchar();97     getchar();98     return 0;99 }