堆
概念
??????堆是具有以下性質(zhì)的完全二叉樹：每個(gè)節(jié)點(diǎn)的值都要大于或等于其左右孩子的值员萍，稱為大頂堆襟铭；或者每個(gè)節(jié)點(diǎn)的值都小于其左右孩子節(jié)點(diǎn)的值贱鄙，稱為小頂堆。
性質(zhì)（完全二叉樹的性質(zhì)）
??????如果對一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹（其深度為logn + 1）的節(jié)點(diǎn)按層次編號(hào)（從第1層到第logn + 1 層潮罪，每層從左到右）康谆，對任一節(jié)點(diǎn)i（1 ≤ i ≤ n）有：
- 如果i=1，則節(jié)點(diǎn)i是二叉樹的根嫉到，無雙親沃暗；如果i > 1，則其雙親是節(jié)點(diǎn) i / 2 何恶。
- 如果2i > n孽锥，則節(jié)點(diǎn) i 無左孩子（i為葉子節(jié)點(diǎn)）；否則其左孩子就是節(jié)點(diǎn)2i 导而。
- 如果 2i+1 > n忱叭，則節(jié)點(diǎn) i 無右孩子隔崎；否則其右孩子就是 2i+1 今艺。
如果將上圖所示的大頂堆和小頂堆用層次遍歷存入數(shù)組，則如下圖所示：
基本思想
??????堆排序就是利用堆進(jìn)行排序的方法（利用大頂堆完成從小到大的排序爵卒，利用小頂堆完成從大到小的排序）虚缎。其基本思想是，將待排序的序列構(gòu)造成一個(gè)大頂堆，此時(shí)整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)实牡，將它一走（其實(shí)就是將其與數(shù)組的末尾元素交換陌僵，此時(shí)末尾元素就是最大值），然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆创坞，就會(huì)得到n個(gè)元素中的次小值碗短。如此反復(fù)進(jìn)行，就可以得到一個(gè)有序序列题涨。（堆排序相當(dāng)于簡單排序算法的升級(jí)偎谁，同屬于 選擇排序類）
堆調(diào)整函數(shù)-heapAdjust
// 已知array[start~end]中記錄的關(guān)鍵字，除array[start]外均滿足堆的定義
// 本函數(shù)用來調(diào)整array[start]關(guān)鍵字纲堵，使array[start~end]成為一個(gè)新的大頂堆
void heapAdjust(int[] array, int start, int end) {
int tmp = array[start];
// i*2+1是i的左子節(jié)點(diǎn)
for (int i = start * 2 + 1; i < end; i = i * 2 + 1) {
// 選擇關(guān)鍵字較大的孩子節(jié)點(diǎn)
if (i < end - 1 && array[i] < array[i + 1]) {
i++;
}
// 若該元素大于子節(jié)點(diǎn)中較大的元素巡雨，那么他就應(yīng)該在此位置
if (tmp > array[i]) {
break;
}
// 父節(jié)點(diǎn)的位置應(yīng)該放置較大的元素
array[start] = array[i];
// 記錄原始start的元素應(yīng)該存放的位置
start = i;
}
array[start] = tmp;
}
堆排序算法
??????堆排序算法的實(shí)現(xiàn)包括兩個(gè)問題：1、如何由一個(gè)無序序列構(gòu)造一個(gè)堆席函；2铐望、如何在輸出堆頂元素后調(diào)整剩余的元素稱為一個(gè)新的堆
void heapSort(int[] array) {
int length = array.length;
// 構(gòu)造一個(gè)大頂堆
for (int i = length/2-1; i >= 0; i--) {
heapAdjust(array, i, length);
}
for (int i = length - 1; i > 0; i--) {
swap(array, 0, i);
// 重新調(diào)整為大頂堆
heapAdjust(array, 0, i - 1);
}
}
此處構(gòu)造大頂堆時(shí)從length/2-1開始是因?yàn)楹罄m(xù)的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，這里所謂的將待排序的序列構(gòu)建成大頂堆其實(shí)就是從下往上茂附，從右到左將每個(gè)非終端節(jié)點(diǎn)當(dāng)作根節(jié)點(diǎn)正蛙，將其和其子樹調(diào)整成大頂堆。
堆排序算法的時(shí)間復(fù)雜度分析
??????堆排序的運(yùn)行時(shí)間主要消耗在初始構(gòu)建堆和在重建堆時(shí)的反復(fù)篩選上营曼。
??????在構(gòu)建堆的過程中因?yàn)槭峭耆鏄鋸淖钕聦幼钣疫叺姆墙K端節(jié)點(diǎn)開始構(gòu)建跟畅，將它與其孩子進(jìn)行比較和若有必要的交換，對于每個(gè)非終端節(jié)點(diǎn)來說溶推，其實(shí)最多進(jìn)行兩次比較和交換操作徊件，因此整個(gè)構(gòu)建過程的時(shí)間復(fù)雜度為O(n)
??????在正式排序時(shí)，第i次取堆頂記錄重建堆時(shí)需要O(log i)的時(shí)間（完全二叉樹的某個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離為log i + 1）蒜危，并且需要取n-1次堆頂記錄虱痕，因此重建堆的時(shí)間復(fù)雜度為O(nlogn)
??????總體來說，堆排序的時(shí)間復(fù)雜度為O(nlogn)辐赞。由于堆排序?qū)υ加涗浀呐判驙顟B(tài)并不敏感部翘，故無論最好最壞和平均狀態(tài)均為O(nlogn)。
由于初始構(gòu)建堆所需的比較次數(shù)較多响委，所以它并不適合待排序序列的個(gè)數(shù)較少的情況
