Java代碼為例講解堆的性質和基本操作以及排序方法

堆的性質
堆是一棵完全二叉樹，實際中可以通過一個數組來實現，它最重要的一個性質是：任意節點都小於（大於）等於其子節點。將根節點最小的堆稱為最小堆，根節點最大的堆稱為最大堆。下圖給出了一個最大堆的示例及其數組表示，可以直觀地看出每個節點都比它的孩子們都要大。

在上圖中可以看到，完全二叉樹的節點可以從根節點編號為1開始按順序排列，對應數組A中的索引（注意此處下標是從1開始的）。給定一個節點i，我們很容易可以得到它的左孩子是2i，右孩子是2i+1，父節點是i/2

堆的基本操作
堆有兩種基本操作（下面以最小堆為例）：
插入元素k：直接將k添加到數組最後，然後向上冒泡（bubble-up）調整堆。向上冒泡操作：將要調整的元素與其父節點比較，如果大於其父節點則交換，直到恢復堆的性質。
提取最值：最值即根元素。然後將其刪除，令根元素=最後的葉子結點元素，然後從根元素開始向下冒泡（bubble-down）調整堆。向下冒泡操作：每次應該從要調整節點，其左右孩子一共三個節點中選擇最小的子節點來交換（如果最小就是其本身就不用交換），直到恢復堆的性質。
實際中經常需要將一個包含n個元素無序數組建立成堆，下面的Heap類中的構造方法將展示如何通過_bubbleDown向下冒泡調整來建堆。堆實質上是一棵完全二叉樹，樹高總為lognlog⁡n，每種基本操作的耗時操作都在於冒泡調整以滿足堆的性質，因此它們的時間複雜度都是O(nlogn)O(nlog⁡n)。
Java示例：

 //上浮public void swim(int k){ while(k/2>=1 && less(pq[k/2],pq[k])){ exch(pq,k/2,k); k=k/2; }}//下沉private void sink() { int k=1; while(2*k<N){ int j=2*k; if(less(pq[j],pq[j+1])) j++; if(less(pq[k],pq[j])) exch(pq,k,j); else break; k = j; }}

堆排序實現原理
分為兩步：
1.把數組排成二叉堆的順序
2.調換根節點和最後一個節點的位置，然後對根節點進行下沉操作。

實現：
可能我的代碼和上面的動畫略有出入，不過基本原理差不多。

 public class HeapSort extends BaseSort { private int N; @Override public void sort(Comparable[] a) { N =a.length-1; int k = N/2; while(k>=1){ sink(a,k); k--; } k = 1; while(k<=N){ exch(a,k,N--); sink(a,k); } }}