堆排序基本思想(最大堆)：
1. 将初始待排序关键字序列(R1,R2....Rn)构建成最大堆，此时堆为初始的无序堆；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
具体实现过程如下：
1. 初始化堆：将R[1,..,n]构造为堆；
2. 将当前无序区的堆顶元素R[1]同该区间的最后一个元素交换，然后将新的无序区调整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
数组{15,17,19,13,22,16,28,30,41,62}
完全二叉树中第一个不是叶子节点的索引：n/2
从第一个不是叶子结点的结点开始调整，即第5个结点22，使以该节点为根的二叉树成为一个最大堆，接着调整第4个结点13,....,一直调整到整棵树的根节点15为止。
值得注意的是：整棵树的索引是从1开始的。
#include#include #include "string.h"#include "stdio.h"#include #include #include #include using namespace std;class Sort {public: int *data; int count;//堆中存在的节点数 int capacity; int* heapSort(int* A, int n) { data = new int[n+1]; capacity = n; for( int i = 0 ; i < n ; i ++ ) { data[i+1] = A[i];//使堆的结点存入data数组中时下标是从1开始 } count = n; //构造堆 for( int i = count/2 ; i >= 1 ; i -- )//从树种第一个不是叶子结点的索引开始 shiftDown(i); for( int i = n-1 ; i >= 0 ; i-- ) A[i] = extractMax(); return A; } int extractMax() { assert(count>0); int ret = data[1];//堆中最大的结点 swap( data[1] , data[count] );//令最大节点与最后一个节点交换 count --;//删除最大节点 shiftDown(1);//对刚刚交换上去的节点进行调整，使其符合最大堆的形式 return ret; } void shiftDown(int k) { while( 2*k <= count )//如果该节点有左孩子 { int j = 2*k;//左孩子的索引值 if( j+1 <= count && data[j+1] > data[j])//如果该节点有右孩子，并且右孩子的值大于左孩子 j ++;//更新为右孩子的索引值 if( data[k] >= data[j])//如果该大于他的孩子结点 break; swap(data[k],data[j]);//否则使该节点与孩子中最大的结点交换 k = j; } }};int main(){ int array[]={ 15,17,19,13,22,16,28,30,41,62}; Sort sort; int len = sizeof(array)/sizeof(array[0]); int* arr = sort.heapSort(array,len); for(int i=0;i