堆的性質
堆是一棵完全二叉樹，實際中可以通過一個數組來實現，它最重要的一個性質是：任意節點都小于（大于）等于其子節點。將根節點最小的堆稱為最小堆，根節點最大的堆稱為最大堆。下圖給出了一個最大堆的示例及其數組表示，可以直觀地看出每個節點都比它的孩子們都要大。
在上圖中可以看到，完全二叉樹的節點可以從根節點編號為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示例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//上浮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.調換根節點和最后一個節點的位置，然后對根節點進行下沉操作。
實現：
可能我的代碼和上面的動畫略有出入，不過基本原理差不多。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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); } }} |
