在 JavaScript 中,可以通過數組來實現一個二叉堆。二叉堆分為最大堆和最小堆兩種類型,本問將以最大堆為例子。
一個二叉堆可以看做是一顆完全二叉樹,每個節點的值都大于等于其子節點的值(對于最大堆而言)。因此,在使用數組來實現二叉堆時,可以使用數組下標來表示完全二叉樹的節點,并滿足以下規則:
- 對于任意節點
i,其左子節點的下標為2i+1,右子節點的下標為2i+2。 - 對于任意節點
i,其父節點的下標為Math.floor((i-1)/2)。
接下來,可以使用數組來實現一個最大堆。具體而言,可以定義一個數組 arr 來保存堆的元素,并定義一些方法來實現堆的常見操作,如插入元素、刪除堆頂元素等。下面是一個簡單的實現示例:
class MaxHeap {
constructor() {
this.heap = [];
}
// 插入元素
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
// 刪除堆頂元素
extractMax() {
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown(0);
}
return max;
}
// 上浮操作
bubbleUp(index) {
const element = this.heap[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (element <= parent) {
break;
}
this.heap[parentIndex] = element;
this.heap[index] = parent;
index = parentIndex;
}
}
// 下沉操作
sinkDown(index) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let largest = index;
if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
largest = left;
}
if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
largest = right;
}
if (largest !== index) {
const temp = this.heap[index];
this.heap[index] = this.heap[largest];
this.heap[largest] = temp;
this.sinkDown(largest);
}
}
}
在上述代碼中,MaxHeap 類定義了一個數組 heap 來保存堆的元素,同時實現了 insert、extractMax、bubbleUp 和 sinkDown 方法,分別用于插入元素、刪除堆頂元素、上浮操作和下沉操作。
在 bubbleUp 方法中,使用循環來不斷將新插入的元素上浮,直到滿足堆的條件;sinkDown 方法中,首先找出當前節點的左子節點和右子節點,然后將當前節點與兩個子節點中的最大值進行比較,如果當前節點的值小于最大值,則交換兩個節點的值,并遞歸進行下沉操作,直到滿足堆的條件。
上面定義類的使用方式如下:
const maxHeap = new MaxHeap();
maxHeap.insert(26);
maxHeap.insert(103);
maxHeap.insert(721);
maxHeap.insert(911);
maxHeap.insert(202);
console.log(maxHeap.heap); // [ 911, 721, 103, 26, 202 ]
const max = maxHeap.extractMax();
console.log(max); // 911
console.log(maxHeap.heap); // [ 721, 202, 103, 26 ]
上面代碼首先創建了一個最大堆 maxHeap,插入了一些元素。然后,調用 extractMax 方法來刪除堆頂元素,得到最大值并打印。最后,打印修改后的堆結構,可以看到堆頂的元素已經被刪除并且堆的結構已經滿足最大堆的條件。