從二叉堆進階到堆排序與優先隊列，前端大佬都這樣學...
一、二叉堆分類
二叉堆根據排序不同可分為大根堆和小根堆。
大根堆
在是完全二叉樹的前提下，其節點值大于其左右子節點值，稱為大根堆。在大根堆中根節點是所有堆節點中的最大值。
小根堆
在是完全二叉樹的前提下，其節點值小于其左右子節點值，稱為小根堆。在小根堆中根節點是所有堆節點中的最小值。
二、二叉堆的存儲
上述闡述了二叉堆其實就是一棵完全二叉樹，然后數據滿足某些特性，那么在編程中應該如何存儲這些數據呢?這些數據間滿足那些關系呢?
1.以數組結構存儲二叉堆
在編程中我們會以數組存儲二叉堆，以上述的最大堆為例，存儲到數組中為如下結構：
2.二叉堆中父子節點間滿足何種關系
既然數據將存儲到數組中，那么就必須知道父子節點之間的關系，即：
(1)在知道父節點的索引的時候必須找到其對應的子節點;
(2)在知道子節點的索引的時候找到其對應的父節點;
如下的二叉堆，設置其根節點索引為0，然后依次遞增：
已知某節點的索引為i，則其左右子節點索引為：
- 左節點索引 = 2 * i + 1
- 右節點索引 = 左節點索引 + 1
已知某節點的索引為i，則其父節點索引為：
- 父節點 = parseInt((i - 1) / 2)
三、堆的基本操作
當遇到二叉堆的時候，我們應該學會如何構建一個大根堆(小根堆)，這個時候就涉及到加堆和減堆的過程，下面讓從加堆和減堆開始，從而使我們能夠絲滑般的了解整個二叉堆的構建過程。(注：下面的例子以大根堆為例)
// 注：此處是封裝的交換數組中元素的方法
// 數組中交換數據
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
1.加堆
加堆的過程實際上就是再往堆里面加入一個新的元素，然后維護該堆結構的過程，實際上就是在數組尾部加入一個元素，然后通過不斷上浮，使其又調整為二叉堆結構的過程。
// 大根堆加堆過程中
function heapInsert(arr, index) {
// 比較當前位置和其父位置，若大于其父位置，則進行交換，并將索引移動到其父位置進行循環，否則跳過
// 結束條件是比其父位置小或者到達根節點處
while (index > 0 && arr[index] > arr[parseInt((index - 1) / 2)]) {
swap(arr, index, parseInt((index - 1) / 2));
index = parseInt((index - 1) / 2);
}
return arr;
}
有了加堆的過程，很容易我們就可以實現創建二叉堆，如下所示：
// 創建二叉堆
function createBigTopHeap(arr) {
for (let i = 0; i < arr.length; i++) {
arr = heapInsert(arr, i);
}
return arr;
}
const arr = [1, 5, 9, 10, 8, 12];
console.log(createBigTopHeap(arr)); // [ 12, 9, 10, 1, 8, 5 ]
2.減堆
減堆的過程就是將堆頂元素A和最后元素B交換，然后刪除A元素并將B元素調整到合適的位置的過程，實際上就是將堆頂數據交換后，下沉數據的過程
// 減堆過程
// size指的是這個數組前多少個數構成一個堆
// 如果想把堆頂彈出，則把堆頂和最后一個數交換，把size減1，然后從0位置經歷一次heapify，調整一下，剩余部分變成大頂堆
function heapify(arr, index, size) {
// 獲取其左節點索引
let left = 2 * index + 1;
while (left < size) {
// 判斷一下左右子節點哪個值最大，獲取其最大值
let largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
// 判斷左右子節點最大值與當前要比較的節點哪個大
largest = arr[index] > arr[largest] ? index : largest;
// 如果最大值索引和傳進來的索引一樣，則該值到達指定位置，直接結束循環
if (index === largest) {
break;
}
// 進行交換，改變索引及其左子節點
swap(arr, index, largest);
index = largest;
left = 2 * index + 1;
}
return arr;
}
const arr = [1, 5, 9, 10, 8, 12];
console.log(createBigTopHeap(arr));
// 交換堆頂數據與最后位置數據
swap(arr, 0, arr.length - 1);
// 通過下沉的方式獲取新的堆結果
console.log(heapify(arr, 0, arr.length - 1));
四、叉堆的用途
因為二叉堆能夠高效的找出最大值和最小值，所以可用于堆排序和構建優先隊列。
1.堆排序
堆排序是常見的一種排序算法，整個堆排序過程如下所示：
- 讓數組變成大根堆。
- 把最后一個位置和堆頂交換。
- 則最大值在最后，則剩余部分做heapify，則重新調整為大根堆，則堆頂位置和該部分最后位置做交換。
- 重復進行，直到減完，則這樣最后就調整完畢，整個數組排完序(為一個升序)。
function heapSort(arr) {
if (arr === null || arr.length === 0) {
return [];
}
// 首先創建大根堆
for (let i = 0; i < arr.length; i++) {
arr = heapInsert(arr, i);
}
let size = arr.length; // 這個值用來指定多少個數組構成堆
// 由于當前已經是大根堆，所以直接交換
swap(arr, 0, --size);
while (size > 0) {
// 重新變成大頂堆
heapify(arr, 0, size);
// 進行交換
swap(arr, 0, --size);
}
return arr;
}
const arr = [1, 5, 9, 10, 8, 12];
console.log(heapSort(arr)); // [ 1, 5, 8, 9, 10, 12
2.優先隊列
普通的隊列是一種先進先出的數據結構，元素在隊列尾追加，而從隊列頭刪除。在優先隊列中，元素被賦予優先級。當訪問元素時，具有最高優先級的元素最先刪除。優先隊列具有最高級先出 (first in, largest out)的行為特征。通常采用堆數據結構來實現。
優先隊列的插入
優先隊列中元素的插入就是上述heapInsert過程，通過將元素添加到數組末尾，然后通過上浮的方式將內容插入到合適位置。
優先隊列中元素的刪除
優先隊列中元素的刪除就是將根節點的元素與最后元素交換，然后將交換后的根節點下沉，調整到合適位置，重新構成二叉堆。
