http://fangjian0423.github.io/2016/04/09/heap-heapsort/
堆的概念：
n個(gè)元素序列 { k1, k2, k3, k4, k5, k6 …. kn } 當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)才會(huì)被稱為堆：
ki <= k2i,ki <= k2i+1 或者 ki >= k2i,ki >= k2i+1 (i = 1,2,3,4 .. n/2)
如果數(shù)組的下表是從0開(kāi)始，那么需要滿足
ki <= k2i+1,ki <= k2i+2 或者 ki >= k2i+1,ki >= k2i+2 (i = 0,1,2,3 .. n/2)
比如 { 1,3,5,10,15,9 } 這個(gè)序列就滿足 [1 <= 3; 1 <= 5], [3 <= 10; 3 <= 15], [5 <= 9] 這3個(gè)條件，這個(gè)序列就是一個(gè)堆。
所以堆其實(shí)是一個(gè)序列(數(shù)組)，如果這個(gè)序列滿足上述條件，那么就把這個(gè)序列看成堆。
堆的實(shí)現(xiàn)通常是通過(guò)構(gòu)造二叉堆，因?yàn)槎娑褢?yīng)用很普遍，當(dāng)不加限定時(shí)，堆通常指的就是二叉堆。
二叉堆的概念：
二叉堆是一種特殊的堆，是一棵完全二叉樹(shù)或者是近似完全二叉樹(shù)，同時(shí)二叉堆還滿足堆的特性：父節(jié)點(diǎn)的鍵值總是保持固定的序關(guān)系于任何一個(gè)子節(jié)點(diǎn)的鍵值，且每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是一個(gè)二叉堆。
當(dāng)父節(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。 當(dāng)父節(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。
上圖中的最小堆對(duì)應(yīng)的序列是： [1,3,5,9,10,15] 滿足最小堆的特性(父節(jié)點(diǎn)的鍵值小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值，并且也滿足堆的性質(zhì) [1 <= 3; 1 <= 5], [3 <= 9; 3 <= 10], [5 <= 15])
上圖中的最大堆對(duì)應(yīng)的序列是： [15,10,9,7,5,3] 滿足最大堆的特性(父節(jié)點(diǎn)的鍵值大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值，并且也滿足堆的性質(zhì) [15 >= 10; 15 >= 9], [10 >= 7; 10 >= 5], [9 >= 3])
堆排序指的是對(duì)堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序的一種算法。其基本思想如下，以最大堆為例：
將數(shù)組序列構(gòu)建成最大堆[ A1, A2, A3 .. An]，這個(gè)堆是一個(gè)剛初始化無(wú)序區(qū)，同時(shí)有序區(qū)為空
堆頂元素A1與最后一個(gè)元素An進(jìn)行交換，得到新的有序區(qū)[An]，無(wú)序區(qū)變成[A1 … An-1]
交換之后可能導(dǎo)致[A1 … An-1]這個(gè)無(wú)序區(qū)不是一個(gè)最大堆，[A1 … An-1]無(wú)序區(qū)重新調(diào)整成最大堆。重復(fù)步驟2，A1與An-1進(jìn)行交換，得到新的有序區(qū)[An,An-1]，無(wú)序區(qū)變成[A1 … An-2].. 不斷重復(fù)，直到有序區(qū)的個(gè)數(shù)為n-1才結(jié)束排序過(guò)程
構(gòu)造堆的過(guò)程如下(以最大堆為例)：
從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)整，遍歷節(jié)點(diǎn)和2個(gè)子節(jié)點(diǎn)，選擇鍵值最大的節(jié)點(diǎn)的鍵值代替父節(jié)點(diǎn)的鍵值，如果進(jìn)行了調(diào)整，調(diào)整之后的兩個(gè)子節(jié)點(diǎn)可能不符合堆特性，遞歸調(diào)整。一直直到調(diào)整完根節(jié)點(diǎn)。
以序列[3,5,15,9,10,1]為例進(jìn)行的堆排序：
首先第1步先把數(shù)組轉(zhuǎn)換成完全二叉樹(shù)：
接下來(lái)是第2、3步構(gòu)造有序區(qū)和無(wú)序區(qū)：
構(gòu)造完之后有序區(qū)的元素依次是：1，3，5，9，10，15
簡(jiǎn)單地使用java寫一下堆排序：
public class HeapSort {
public static void maxHeapify(int[] arr, int size, int index) {
int leftSonIndex = 2 * index + 1;
int rightSonIndex = 2 * index + 2;
int temp = index;
if(index <= size / 2) {
if(leftSonIndex < size && arr[temp] < arr[leftSonIndex]) {
temp = leftSonIndex;
}
if(rightSonIndex < size && arr[temp] < arr[rightSonIndex]) {
temp = rightSonIndex;
}
// 左右子節(jié)點(diǎn)的值存在比父節(jié)點(diǎn)的值更大
if(temp != index) {
swap(arr, index, temp); // 交換值
maxHeapify(arr, size, temp); // 遞歸調(diào)整
}
}
}
public static void heapSort(int[] arr, int size) {
// 構(gòu)造成最大堆
buildMaxHeap(arr, arr.length);
for(int i = size - 1; i > 0; i --) {
// 先交換堆頂元素和無(wú)序區(qū)最后一個(gè)元素
swap(arr, 0, i);
// 重新調(diào)整無(wú)序區(qū)
buildMaxHeap(arr, i - 1);
}
}
public static void buildMaxHeap(int[] arr, int size) {
for(int i = size / 2; i >= 0; i --) { // 最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)整
maxHeapify(arr, size, i);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = { 3, 5, 15, 9, 10, 1};
System.out.println("before build: " + Arrays.toString(arr)); // before build: [3, 5, 15, 9, 10, 1]
buildMaxHeap(arr, arr.length);
System.out.println("after build: " + Arrays.toString(arr)); // after build: [15, 10, 3, 9, 5, 1]
heapSort(arr, arr.length);
System.out.println("after sort: " + Arrays.toString(arr)); // after sort: [1, 3, 5, 9, 10, 15]
}
}
添加
在最大堆[ 15,10,9,7,5,3 ]上添加一個(gè)新的元素 11 ，執(zhí)行的步驟如下：
刪除
在最大堆[ 15,10,9,7,5,3 ]上刪除元素 10 ，執(zhí)行的步驟如下：
