完全二叉树之堆

• 用堆降序排序

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

   

完全二叉树之堆

原文：https://www.cnblogs.com/zenghaifan/p/15007633.html