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