堆是一种特殊的基于树的数据结构,满足堆属性。
它是一棵完全二叉树,这意味着除了最后一层是从左到右填充之外,树的所有层都被完全填充。
堆有两种类型:
最大堆:
在最大堆中,对于任何给定节点 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中文网其他相关文章!