概念自周原老师

是一种直接选择型排序的一种改进算法
简单选择排序算法+利用连续多次查找最大记录的特性=》堆排序算法
发

在操作系统中，将多个进程防震一个队列中，每个过程有一个优先级，总是出队优先级最高的进程执行
采用优先队列，用堆来实现！

基本思路

在无序区中选出最小（大）记录R[K]放到全局有序区的后面
采用堆方法来选出最小记录

堆的定义

一个序列R【1..n】，关键字为k1,k2,....,kn.
该序列满足以下性质：
1、ki<=k2i且ki<=k2i+1
2、ki<=k2i且ki<=k2i+1 (1<=I<=(n/2))
满足第一种情况的是小根堆
满足第二种情况的是大根堆

筛选算法建堆

把堆看成一个完全二叉树
我们堆这颗树进行调整，使整个二叉树成为一个堆
从最后一个分支节点往下调整为初始大根堆

过程

不断在无序区找最值并放入有序区中
然后重新调整堆直到排序结束

程序

筛选或调整算法

void sift(RecType R[], int low ,int high) //调整堆的算法，该样例是将小的数字向下调整
{
      int I=low, j=I*2; //R[I]是R[I]的左孩子
      RecType tmp=R[I];
      while (j<=high)
      {
            if (j<high && R[j].key<r[j+1].key) j++; //指向大孩子
            if (tmp.key<R[j].key)
            {
                  R[I]=R[j];
                  I=j;
                  j=2*I;
            }
            else break;
      }
      R[I]=tmp;
}

堆排序算法

void HeapSort(RecType R[], int n)
{
      int I; RecType tmp;
      for (I=n/2;i>=1;i--)  //循环建立初始堆
            sift(R, i, n);
      for (i=n; i>=2; i--)  //进行n-1次循环，完成堆排序
      {
            temp=R[1]; //将交换最值R[1]到最后
            R[1]=R[i]; R[i]=tmp;
            sift(R, 1, i-1); //筛选R[1]节点，得到i-1节点的堆（得到最值）
      }
}