堆是一種特殊的基於樹的資料結構，滿足堆屬性。
它是一棵完全二元樹，這意味著除了最後一層是從左到右填充之外，樹的所有層都被完全填充。
堆有兩種：
最大堆：
在最大堆中，對於任何給定節點 I，I 的值大於或等於其子節點的值。
對於二元樹中的所有節點，此屬性必須為 true。最高值（最大值）位於樹的根部。
最小堆：
在最小堆中，對於任何給定節點 I，I 的值小於或等於其子節點的值。
對於二元樹中的所有節點，此屬性必須為 true。最低值（最小值）位於樹的根部。
我們可以稱它們為優先權佇列，因為每次執行插入和刪除操作時，它都會分別 bubbleUp 和 bubbleDown。
我們可以在數組中實現相同的功能，但是如何計算 leftChildIndex、rightChildIndex 和 ParentIndex？
公式
為了生小孩
2i+1（左）
2i+2（右）
取得父母
i-1/2
下面我新增了一個 minHeap 的實現，請檢查。
class MinHeap {
constructor() {
this.data = [];
this.length = 0;
}
insert(value) {
this.data.push(value);
this.length++;
this.bubbleUp(this.length-1);
}
bubbleUp(index) {
if (index == 0) {
return ;
}
const parentIndex = this.getParentIndex(index);
const parentValue = this.data[parentIndex];
const value = this.data[index];
if (parentValue > value) {
this.data[parentIndex] = this.data[index];
this.data[index] = parentValue;
this.bubbleUp(parentIndex);
}
}
getParentIndex(index) {
return Math.floor((index-1)/2);
}
getLeftChildIndex(index) {
return 2*index + 1;
}
getRightChildIndex(index) {
return 2*index + 2;
}
bubbleDown(index) {
if (index >= this.length) {
return;
}
const lIndex = this.getLeftChildIndex(index);
const rIndex = this.getRightChildIndex(index);
const lValue = this.data[lIndex];
const rValue = this.data[rIndex];
const value = this.data[index];
if (lValue < rValue && lValue < value) {
// swap
this.data[index] = this.data[lIndex];
this.data[lIndex] = value;
this.bubbleDown(lIndex);
} else if (rValue < lValue && rValue < value) {
this.data[index] = this.data[rIndex];
this.data[rIndex] = value;
this.bubbleDown(rIndex)
}
}
delete() {
if (this.length === 0) {
return -1;
}
const out = this.data[0];
if (this.length == 1) {
this.data = [];
this.length = 0;
return out;
}
this.data[0] = this.data[this.length-1];
this.length--;
this.bubbleDown(0);
}
}
const test = new MinHeap();
test.insert(50);
test.insert(100);
test.insert(101);
test.insert(20);
test.insert(110);
console.log(test)
test.delete();
console.log('---------After Delete -------')
console.log(test)
/*
MinHeap { data: [ 20, 50, 101, 100, 110 ], length: 5 }
---------After Delete -------
MinHeap { data: [ 50, 100, 101, 110, 110 ], length: 4 }
*/
如果您有任何疑問，請隨時與我聯繫。
以上是堆|使用Javascript實作優先權隊列的詳細內容。更多資訊請關注PHP中文網其他相關文章！
