堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆节点的访问

通常堆是通过一维数组来实现的。在起始阵列为 0 的情形中：

堆的根节点（即堆积树的最大值）存放在阵列位置 1 的地方;

　　注意：不使用位置 0，否则左子树永远为 0^[2]

父节点i的左子节点在位置 (2*i);
父节点i的右子节点在位置 (2*i+1);
子节点i的父节点在位置 floor(i/2);

对vector中的数据进行堆排序：

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 void HeapAdjust(vector<int> &H,int s,int m)
 5 {
 6     int rc=H[s];
 7     for(int i=s*2;i<=m;i*=2)
 8     {
 9         if(i<m&&i+1<m&&H[i]>H[i+1])//顺着较小的路线向下调整,(这里是要建小顶堆)
10             i++;
11         if (rc<H[i])//下面的叶子比堆顶的值大
12             break;
13 
14         H[s]=H[i];//上移子节点
15         s=i;
16 
17     }
18 
19     H[s]=rc;//插入堆顶值
20 
21 
22 }
23 
24 void HeapSort(vector<int> &H)
25 {//对vector<int> H,从H[1]....H[H.size()-1]进行堆排序
26 
27     for (int i=(H.size()-1)/2;i>=1;i--)
28     {
29         HeapAdjust(H,i,H.size()-1);//从最后一个非叶子节点开始向上调整堆，建立堆
30     }
31 
32     for(int i=H.size()-1;i>1;i--)
33     {
34         int temp;
35         temp=H[1];
36         H[1]=H[i];
37         H[i]=temp;//把堆顶交换到尾部
38 
39         //在对H从H[1].....H[i-1]进行调整
40         HeapAdjust(H,1,i-1);
41 
42     }
43 
44 }
45 
46 int main()
47 {
48     vector<int>  v;
49     v.push_back(0);//v[0]不用
50     v.push_back(2);
51     v.push_back(5);
52     v.push_back(3);
53     v.push_back(1);
54 
55     HeapSort(v);
56     for (int i=1;i<v.size();i++)
57     {
58         cout<<v[i]<<endl;
59     }
60     return 1;
61 }

结果：