堆
堆排序需要用到二叉堆，在開始之前均澳，我們先來(lái)了解一下什么是二叉堆恨溜。
當(dāng)二叉樹滿足滿足如下條件時(shí)，我們說(shuō)這個(gè)二叉樹是堆有序的：
- 每一個(gè)父結(jié)點(diǎn)的值都比它的子結(jié)點(diǎn)大（稱為大頂堆）或姓仪啊（稱為小頂堆）
- 子結(jié)點(diǎn)的大小與其左右位置無(wú)關(guān)
堆有序的二叉樹糟袁，也可稱為二叉堆。二叉堆是最常見的堆結(jié)構(gòu)躺盛，因此也常將二叉堆直接稱為堆项戴，可以采用如下兩種方式來(lái)表示二叉堆
- 使用指針，二叉樹的每個(gè)結(jié)點(diǎn)需存儲(chǔ)三個(gè)指針槽惫，分別指向其父結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)
- 使用數(shù)組周叮，對(duì)二叉樹做層序遍歷辩撑，按層級(jí)順序放入數(shù)組中，根結(jié)點(diǎn)在數(shù)組索引0的位置存放仿耽，其子結(jié)點(diǎn)分別在索引1和2的位置合冀，1和2個(gè)子結(jié)點(diǎn)分別在位置3、4和5项贺、6中存放君躺，以此類推
就排序來(lái)講，其所需處理的數(shù)據(jù)較為連續(xù)开缎，沒有空隙棕叫，可用完全二叉樹來(lái)表示。對(duì)于完全二叉樹奕删，采用數(shù)組的表示方法也更方便些俺泣，下圖展示了采用數(shù)組實(shí)現(xiàn)的兩個(gè)二叉堆。
對(duì)于數(shù)組實(shí)現(xiàn)的二叉堆完残，索引為k的結(jié)點(diǎn)的父結(jié)點(diǎn)的索引為(k-1)/2伏钠，它的子結(jié)點(diǎn)的索引分別為2k+1和2k+2。
堆有序化
以大頂堆為例谨设，有序化的過(guò)程中我們會(huì)遇到兩種情況
- 在堆底加入一個(gè)較大元素時(shí)贝润，我們需要由下至上恢復(fù)堆的順序
- 當(dāng)將根結(jié)點(diǎn)替換為一個(gè)較小元素時(shí)，我們需要由上到下恢復(fù)堆的順序
由下至上的堆有序化（上嘎料）
如果堆的有序狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變的比它的父結(jié)點(diǎn)更大而被打破打掘，就需要通過(guò)將它與它的父結(jié)點(diǎn)交換來(lái)恢復(fù)堆有序。交換后鹏秋，這個(gè)結(jié)點(diǎn)比它的兩個(gè)子結(jié)點(diǎn)都大尊蚁，但這個(gè)結(jié)點(diǎn)仍然可能比它現(xiàn)在的父結(jié)點(diǎn)更大。我們可以一遍遍的用同樣的方式來(lái)將其向上移動(dòng)侣夷，直到遇到一個(gè)比它更大的父結(jié)點(diǎn)或到達(dá)了堆的根結(jié)點(diǎn)横朋，如下圖所示。
上浮操作對(duì)應(yīng)的代碼如下
private void swim(Integer arr[], int k) {
while(k > 0 && arr[(k - 1) / 2] < arr[k]) { //若k>0且索引為k的結(jié)點(diǎn)大于其父結(jié)點(diǎn)時(shí)琴锭，將該結(jié)點(diǎn)與其父結(jié)點(diǎn)交換
swap(arr, k, (k - 1) / 2);
k = (k - 1) / 2;
}
}
由上至下的堆有序化（下沉）
如果堆的有序狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變的比它的某個(gè)子結(jié)點(diǎn)更小而被打破，就需要通過(guò)將它和它的子結(jié)點(diǎn)中較大者交換位置來(lái)恢復(fù)堆有序衙传。交換可能會(huì)在子結(jié)點(diǎn)處繼續(xù)打破堆的有序狀態(tài)决帖，此時(shí)可以采用相同的方式，將結(jié)點(diǎn)向下移動(dòng)直到它的子結(jié)點(diǎn)都比它小或是到達(dá)了堆的底部蓖捶，如下圖所示地回。
下沉操作對(duì)應(yīng)的代碼如下
private void sink(Integer arr[], int k) {
while(2 * k + 1 <= arr.length - 1) {//若k存在子結(jié)點(diǎn)，則進(jìn)入循環(huán)
int j = 2 * k + 1; //獲取k的第一個(gè)子結(jié)點(diǎn)
if (j < arr.length - 1 && arr[j] < arr[j + 1]) {//若存在兩個(gè)子結(jié)點(diǎn)，則找到其中較大的子結(jié)點(diǎn)
j++;
}
if (arr[j] > arr[k]) {//若k的較大子結(jié)點(diǎn)比k大刻像，則交換它們的位置
swap(arr, j, k);
k = j;
}
}
}
堆排序
在介紹完堆的數(shù)據(jù)結(jié)構(gòu)和操作方式后畅买，我們來(lái)看堆排序是如何進(jìn)行的。
堆的構(gòu)造
- 將原數(shù)組看做堆的話细睡，則最后一個(gè)分支結(jié)點(diǎn)（含有子結(jié)點(diǎn)的結(jié)點(diǎn)）在原數(shù)組中的索引為 (n-1)/2 -1
- 從(n-1)/2-1向前依次執(zhí)行下沉操作谷羞，從而得到堆有序的數(shù)組
堆的排序
- 取出堆的根結(jié)點(diǎn)，與數(shù)組最后一個(gè)元素交換溜徙。交換后堆有序狀態(tài)可能會(huì)被打破洒宝，需要在新的根結(jié)點(diǎn)進(jìn)行下沉操作，使其恢復(fù)為堆有序狀態(tài)萌京。此時(shí)數(shù)組中最大(大頂堆)/最小(小頂堆)的值存放在數(shù)組末位，除它以外的最 大/小 值位于堆頂宏浩。
- 從數(shù)組中排除最后一個(gè)元素知残，重復(fù)步驟2，直到數(shù)組中的元素全部排除時(shí)比庄，完成排序
public static void heapSort(Integer arr[]) {
int n = arr.length;
//堆的構(gòu)造,對(duì)每一個(gè)含有孩子的結(jié)點(diǎn)做下沉操作,得到大頂堆
for (int i = (n-1) /2 -1; i >= 0; i--) {
heapSink(arr, i, n);
}
printArr(arr, "大頂堆");
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapSink(arr, 0, i);
}
printArr(arr, "堆排序");
}
public static void heapSink(Integer arr[], int i, int length) {
while(2 * k + 1 <= length - 1) {//若k存在子結(jié)點(diǎn)求妹，則進(jìn)入循環(huán)
int j = 2 * k + 1; //獲取k的第一個(gè)子結(jié)點(diǎn)
if (j < length - 1 && arr[j] < arr[j + 1]) {//若存在兩個(gè)子結(jié)點(diǎn)，則找到其中較大的子結(jié)點(diǎn)
j++;
}
if (arr[j] > arr[k]) {//若k的較大子結(jié)點(diǎn)比k大佳窑，則交換它們的位置
swap(arr, j, k);
k = j;
}
}
}
堆排序動(dòng)態(tài)圖
小結(jié)
堆排序算法也是一種選擇排序算法制恍，整體由堆的構(gòu)建、堆的交換與下沉兩個(gè)步驟組成神凑。其中堆的構(gòu)建需要比較(n-1)/2-1次下沉净神，每次下沉至多交換一次，時(shí)間復(fù)雜度為O(n)溉委；堆的交換與下沉中需交換n次鹃唯，下沉依次需要執(zhí)行\log_2(n-1),log_2(n-2)...1次交換，近似為Nlog_2N瓣喊。因此堆排序的時(shí)間復(fù)雜度為O(N\log_2N)
