正文之前
這一篇文章介紹一下堆的概念，以及堆排序
- 基本概念、最大/最小堆
- 堆排序
- 分析
正文
1. 什么是堆
堆不是單獨(dú)的一種結(jié)構(gòu)，而是一種樹(shù)狀數(shù)據(jù)結(jié)構(gòu)攀甚，通過(guò)二叉堆來(lái)實(shí)現(xiàn)，二叉堆也就是二叉樹(shù)的一種岗喉，講白了就是類(lèi)似二叉樹(shù)秋度，只不過(guò)滿足：
除了最底層，其他層全滿钱床，最底層按照從左至右的順序填入節(jié)點(diǎn)（完全二叉樹(shù)）
父節(jié)點(diǎn)大于等于或小于等于子節(jié)點(diǎn)荚斯，這兩種情況就成為了最大堆/最小堆的定義：
最大堆：任意節(jié)點(diǎn)大于等于它的所有后裔（不僅是子節(jié)點(diǎn)，還有子節(jié)點(diǎn)的子節(jié)點(diǎn)等等）查牌，最大節(jié)點(diǎn)在堆頂
最小堆：任意節(jié)點(diǎn)小于等于它的所有后裔事期，最小節(jié)點(diǎn)在堆頂
還有一種叫法是大頂堆/小頂堆
給個(gè)圖吧：
2. 堆排序
堆排序的步驟是這樣的：
- 用給定數(shù)組構(gòu)建堆
- 一個(gè)循環(huán)，每次選擇堆頂元素纸颜，調(diào)換至末尾刑赶，然后縮小范圍（相當(dāng)于取出隊(duì)首元素，添加至末尾懂衩，一輪循環(huán)后，數(shù)組就有序了）
首先我們先來(lái)寫(xiě)一下確定節(jié)點(diǎn)位置的代碼：
/**
* 因?yàn)橄聵?biāo)是從 0 開(kāi)始的，在獲取節(jié)點(diǎn)
* 的時(shí)候要多 + 1
* @param node 給定節(jié)點(diǎn)的位置
* @return 對(duì)應(yīng)節(jié)點(diǎn)位置
*/
public int leftNode(int node){
return 2 * node + 1;
}
public int rightNode(int node){
return 2 * node + 2;
}
public int parentNode(int node){
return (node - 1) / 2;
}
這里的 parentNode() 方法沒(méi)有用到浊洞，但是這個(gè)計(jì)算父節(jié)點(diǎn)的方式下面要用到牵敷，然后我們來(lái)寫(xiě)調(diào)整堆的方法，采用遞歸的方法法希，每一次遞歸我們只針對(duì)某個(gè)節(jié)點(diǎn)以及它的子節(jié)點(diǎn)：
public void maxHeapify(int[] heap, int length, int node){
//獲取左右節(jié)點(diǎn)
int left = leftNode(node);
int right = rightNode(node);
//當(dāng)前最大節(jié)點(diǎn)（堆頂）
int largest = node;
//如果左子節(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值枷餐，就改變 largest 的指向
if (left < length && heap[left] > heap[largest]){
largest = left;
}
//如果右子節(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值，就改變 largest 的指向
if (right < length && heap[right] > heap[largest]){
largest = right;
}
//如果 largest 的指向改變了苫亦，就說(shuō)明要調(diào)整堆毛肋，調(diào)換兩個(gè)元素的位置
if (largest != node){
int temp = heap[node];
heap[node] = heap[largest];
heap[largest] = temp;
} else {
return;
}
maxHeapify(heap, length, largest);
}
然后是構(gòu)建堆的方法，就像在上面的代碼中定義的尋找父節(jié)點(diǎn)位置的方法一樣屋剑，(heap.length - 1) 代表的是堆中最后一個(gè)節(jié)點(diǎn)位置润匙，(heap.length - 1) / 2 是最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的位置，從這里開(kāi)始構(gòu)建堆唉匾，避免多次不必要的遞歸孕讳，提高效率：
public void buildHeap(int[] heap){
for (int i = (heap.length - 1) / 2; i >= 0 ; i--) {
maxHeapify(heap, heap.length, i);
}
}
最后便是堆排序的代碼：
public void heapSort(int[] heap){
for (int i = heap.length - 1; i > 0; i--) {
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
maxHeapify(heap, i, 0);
}
}
劃重點(diǎn)：這里之所以要用 i 來(lái)代替 heap.length，是因?yàn)槲覀円M從堆頂刪除節(jié)點(diǎn)巍膘，實(shí)際上并沒(méi)有刪除厂财，只是把它換到了末尾，所以通過(guò)堆大小 - 1 來(lái)達(dá)到模擬刪除的效果
畫(huà)了個(gè)堆排序的過(guò)程圖：
數(shù)組 [3,5,2,6,4,1,10,7,9,8] 構(gòu)建完后就是圖中 1 的堆峡懈，然后把 4 和 10 對(duì)調(diào)璃饱，再調(diào)整堆，得到圖中 2 的堆肪康，把 6 和 9 對(duì)調(diào)荚恶，然后調(diào)整堆，以此類(lèi)推：
接下來(lái)是計(jì)算的結(jié)果：
構(gòu)建最大堆進(jìn)行排序的結(jié)果是升序梅鹦，因?yàn)榇蟮墓?jié)點(diǎn)在末尾裆甩，如果要降序排列，就構(gòu)建最小堆
3. 分析
- 時(shí)間復(fù)雜度：
時(shí)間都花在了一開(kāi)始的構(gòu)建堆和接下來(lái)的調(diào)整堆過(guò)程齐唆，對(duì)于 n 個(gè)數(shù)：
首先是新建堆嗤栓，時(shí)間復(fù)雜度 O(n)
每一次的調(diào)整堆都是 logn，總共有 n - 1 次箍邮，為 (n - 1) * logn = nlogn - logn
所以堆排序的時(shí)間復(fù)雜度是 O(nlogn)
- 空間復(fù)雜度
O(1)茉帅，因?yàn)槭窃嘏判颍瑳](méi)有借助其它輔助結(jié)構(gòu)
- 穩(wěn)定性
不穩(wěn)定
