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

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

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

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

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

void   HeapAdjust(Elem   &e,int   s,int   m) 
{//e中s...m的元素除e[s]之外已經(jīng)滿足堆的定義（e[i] <=e[2*i]&&e[i] <=e[2*i+1] 
  //或e[i]> =e[2*i]&&e[i]> =e[2*i+1]),調(diào)整e[s]使的e[s...m]成為一個大頂堆。 
      selem=e[s]; 
      for(i=2*s;i <=m;i*=2)//沿著值較大的元素（結(jié)點(diǎn)）向下篩選 
      { 
            if(i <m   &&   e[i] <e[i+1])++i;//i為值較大的元素下標(biāo) 
            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);//調(diào)整1..i-1的元素成為大頂堆 
      }     
}


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

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