堆是一種特殊的基於樹的資料結構,滿足堆屬性。
它是一棵完全二元樹,這意味著除了最後一層是從左到右填充之外,樹的所有層都被完全填充。
堆有兩種:
最大堆:
在最大堆中,對於任何給定節點 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中文網其他相關文章!