堆排序

什么是堆

堆是一种特殊的数据结构，其本质是一棵用数组存储的一棵完全二叉树。

堆的性质

一个结点，对应数组元素Heap[i],其父结点为Heap[i/2]，左子结点Heap[2*i],右子结点Heap[2*i+1]。
一个堆中，任何一个结点必须大于或小于其子结点。大于的称大根堆，小于的称小根堆。

堆的操作

下列操作均以小根堆为例

插入

将新结点放于队尾，为了使堆的性质2成立，直接模拟即可，时间复杂度O(logn):
1. 如果当前结点大于等于父结点，或者当前节点已经是根结点，结束。
2. 否则将其与父节点交换，转1。

程序实现

 1 void Put(int x)
 2 {
 3     int Son;
 4      Heap[++Len]=x;//放于堆底
 5     Son=Len;
 6     while(Len!=1&Heap[Son/2]>Heap[Son])
 7     {//如果还不是根结点并且堆的性质仍然不满足
 8         Swap(Heap[Son],Heap[Son/2]);//交换
 9         Son/=2;//转移当前结点
10     }
11 }

删除

将堆底的结点来替换根结点，然后向下调整，时间复杂度O(logn):
1. 将堆底的结点替换根结点，标记为当前结点
2. 若当前结点比两个子结点都小，则对的性质满足，退出。若其已经是叶子结点，退出。
3. 否则去两个子结点中最小的与交换，转2。为什么要取最小的与之交换呢？因为如果取的事大的，则作为另一个子结点的父结点时，一定会大于它，不满足对的性质。

程序实现

 1 int Get()
 2 {
 3     int re=Heap[1],Son,Fa;//存下根结点的值，以便返回
 4     Heap[1]=Heap[Len];//将尾结根结点点替换
 5     Len--;//删除了，肯定堆长要少一个嘛
 6     Fa=1;//当前父结点，
 7     while(Fa*2<=Len)//保证它有子结点
 8     {
 9         if(Fa*2+1>Len||Heap[Fa*2]<Heap[Fa*2+1])//选左子结点的条件是比右子结点小，或者当前父节点没有右子结点
10             Son=Fa*2;
11         else Son=Fa*2+1;//若右子结点比左子结点小，选它
12         if(Heap[Fa]>Heap[Son])//如果最小的都没当前父节点小，那就已经是一个堆了
13         {
14             Swap(Heap[Fa],Heap[Son]);//交换
15             Fa=Son;//转移
16         }
17         else //既然已经是一个堆了，直接退出
18             break;
19     }
20     return re;//返回原根结点的值
21 }

建堆

第一种方法：将每一个元素都插入堆，时间复杂度O(nlogn)

核心代码

1 for(int i=1;i<=n;++i)
2 {
3     scanf("%d",&a);
4     Put(a);
5 }

第二种方法将所有元素直接排序，则一定满足堆的性质。

核心代码

 1 sort(a+1,a+n+1);

堆排序

堆的性质保证，堆的根结点一定是堆中最小的。所以，堆常用作选出最值的优化。
最典型的例子就是堆排序了。
堆排序其实是对选择排序的优化。
选择排序的思想是每一次循环都选出最小的。

选排代码

1 for(int i=1;i<=n-1;++i)
2     for(int j=i+1;j<=n;++j)
3         if(a[i]>a[j])
4             swap(a[i],a[j]);

而堆排也是一样的。堆排利用堆的性质，每一次都输出根结点并删去，单次时间复杂度O(logn)。那么只需n次即可完成排序，代码如下：

 1 #include<cstdio>
 2 
 3 int Heap[1000001],Len;
 4 
 5 void Swap(int &x, int &y)
 6 {
 7     int s=x;
 8     x=y;
 9     y=s;
10 } 
11 
12 void Put(int x)
13 {
14     int Son;
15      Heap[++Len]=x;
16     Son=Len;
17     while(Len!=1&Heap[Son/2]>Heap[Son])
18     {
19         Swap(Heap[Son],Heap[Son/2]);
20         Son/=2;
21     }
22 }
23 
24 int Get()
25 {
26     int re=Heap[1],Son,Fa;
27     Heap[1]=Heap[Len];
28     Len--;
29     Fa=1;
30     while(Fa*2<=Len)
31     {
32         if(Fa*2+1>Len||Heap[Fa*2]<Heap[Fa*2+1])
33             Son=Fa*2;
34         else Son=Fa*2+1;
35         if(Heap[Fa]>Heap[Son])
36         {
37             Swap(Heap[Fa],Heap[Son]);
38             Fa=Son;
39         }
40         else
41             break;
42     }
43     return re;
44 }
45 
46 int main()
47 {
48 //    freopen("duipai.in","r",stdin);
49 //    freopen("duipai.out","w",stdout);
50     int n,a;
51     scanf("%d",&n);
52     for(int i=1;i<=n;++i){
53         scanf("%d",&a);
54         Put(a);
55     }
56     for(int i=1;i<=n-1;++i)
57         printf("%d ",Get());
58     printf("%d",Get());
59     putchar('
');
60     fclose(stdin);fclose(stdout);
61     return 0;
62 }