堆排序（Heapsort）是指利用 这种数据结构所设计的一种排序算法。堆是一个近似 的结构，并同时满足

堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆节点的访问

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

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

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

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

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

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 void HeapAdjust(vector
       
         &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
        
         
          H[i+1])//顺着较小的路线向下调整,(这里是要建小顶堆)10             i++;11         if (rc
          

&H)25 { //对vector

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

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