估計還要問問：什么是堆，什么是堆排序？堆與計算機分配內存的堆相同嗎？
很多資料給出：堆的定義是
（1）、n個關鍵字序列（Kl，K2，…，Kn）稱為(Heap)，當且僅當該序列滿足如下性質(簡稱為堆性質)：
ki≤K2i且ki≤K2i+1 或  Ki≥K2i且ki≥K2i+1 (1≤i≤ n) //ki相當于二叉樹的非葉結點，K2i則是左孩子，k2i+1是右孩子 

（2）若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹： 　　樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。

（3）、根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆，又稱最小堆。根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆，又稱最大堆。

（4）、堆中任一子樹亦是堆。
（5）、堆可以視為一棵完全的二叉樹，完全二叉樹的一個“優秀”的性質是，除了最底層之外，每一層都是滿的，這使得堆可以利用數組來表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個結點對應數組中的一個元素。

那么堆排序呢？
堆排序其實就是將一組無序的序列變成堆的過程、下面我們一起看看堆排序的算法。
2、堆排序
以最大堆為例，步驟為：
　　① 先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區 　　② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最后一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key 　　③由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 　　…… 　　直到無序區只有一個元素為止。  
將一個無序的序列建成堆的過程實際上是一個反復篩選的過程。若將此序列看作是一棵完全二叉樹，則最后一個非終端結點是[n/2](不大于n/2的整數），因此篩選過程只需從[n/2]開始。要建成一個大頂堆，即先選擇一個值最大的元素并與序列中的最后一個元素交換，然后對序列前n-1元素進行篩選，從新調整為一個大頂堆，直到結束。 
算法描述如下： 
  
typedef   int[]   Elem;//采用順序存儲表示完全二叉樹 

void   HeapAdjust(Elem   &e,int   s,int   m) 
{//e中s...m的元素除e[s]之外已經滿足堆的定義（e[i] <=e[2*i]&&e[i] <=e[2*i+1] 
  //或e[i]> =e[2*i]&&e[i]> =e[2*i+1]),調整e[s]使的e[s...m]成為一個大頂堆。 
      selem=e[s]; 
      for(i=2*s;i <=m;i*=2)//沿著值較大的元素（結點）向下篩選 
      { 
            if(i <m   &&   e[i] <e[i+1])++i;//i為值較大的元素下標 
            if(selem> =e[i])break; 
            e[s]=e[i]; 
            s=i; 
        } 
      e[s]=selem; 
} 

void   HeapSort(Elem   &e) 
{//對順序表排序 
    for(i=e.length/2;i> 0;--i) 
            HeapAdjust(e,i,e.length); 
    for(i=e.length;i> 1;--i) 
    { 
          temp=e[1];                     //將堆中的最后一個元素與第一個元素交換 
          e[1]=e[i]; 
          e[i]=temp; 
          HeapAdjust(H,1,i-1);//調整1..i-1的元素成為大頂堆 
      }     
}


/////////////////////////////////////////////////////////////
使用堆排序注意的問題：：：
1、序列是從1開始的。，注意定義，R[1..n]，故要空出R[0]。
2、堆排序算法分為兩部分：建立大頂堆和排序。
3、排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。
4、由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。 5、　堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。

問題：當序列空間為R[0,1....n]；時，該怎么去使用堆排序呢？元素后移一位，這明顯不是一個好方法。