堆排序（Heapsort）是利用堆这种数据结构的排序算法。堆是一个近似完全二叉树的结构。
堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆节点的访问
通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
- 堆的根节点（即堆积树的最大值）存放在数组位置 1 的地方;
注意：不使用位置 0，否则左子树永远为 0[2]
- 父节点i的左子节点在位置 (2*i);
- 父节点i的右子节点在位置 (2*i+1);
- 子节点i的父节点在位置 floor(i/2);
堆的操作
在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：
- 最大堆调整（Max_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点
- 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根结点，并做最大堆调整的递归运算
数组堆积排序
1 #include<iostream> 2 using namespace std; 3 4 //筛选法 5 void sift(int E[],int j,int length) 6 { 7 int i=j; 8 int c = 2*i+1;//数据从0开始 9 10 while(c < length) 11 { 12 if((c+1<length)&&(E[c]<E[c+1]))//左孩子<右孩子 时，取大的（右孩子） 13 c++; 14 if(E[i]>E[c]) 15 break;//此节点数据已经比孩子节点数据大 则停止循环 16 else 17 { 18 int t=E[i]; 19 E[i]=E[c]; 20 E[c]=t; 21 22 i=c;//继续重复上述操作，直到孩子节点小于此节点或到数的最后一层 23 c = 2*i+1; 24 } 25 } 26 } 27 //堆排序 28 void HeapSort(int E[],int n)//第二个参数是数组长度 29 { 30 //初始化堆 31 for(int i=n/2;i>=0;i--)//i=n/2是从倒数第二行开始 32 sift(E,i,n); 33 34 for(int i=0;i<n;i++)//所有的元素 35 { 36 //数组的0号位置与堆内剩余的数据中最后一个交换位置 37 int t=E[n-i-1]; 38 E[n-i-1]=E[0]; 39 E[0]=t; 40 41 sift(E,0,n-i-1);//每次都是数组的0号位置 42 } 43 } 44 45 int main() 46 { 47 int E[]={3, 5, 3, 6, 4, 7, 5, 7, 4}; 48 cout<<"原始序列："<<endl; 49 for(int i=0;i<sizeof(E)/sizeof(int);i++) 50 cout<<E[i]<<" "; 51 cout<<endl; 52 53 HeapSort(E,sizeof(E)/sizeof(*E)); 54 55 cout<<"堆排序后的序列："<<endl; 56 for(int i=0;i<sizeof(E)/sizeof(int);i++) 57 cout<<E[i]<<" "; 58 cout<<endl; 59 60 return 0; 61 }
本文转自cococo点点博客园博客，原文链接：http://www.cnblogs.com/coder2012/archive/2012/10/09/2717314.html，如需转载请自行联系原作者