最大堆,又称大根堆,大顶堆,JavaScript 实现大根堆的代码。
![JavaScript 最大堆完全二叉树结构示意图](//cdn.mtf6.com/202204101751473485_c_w_1280.png)
最大堆
- 完全二叉树:从上到下,从左到右,编号为 i 的节点与满二叉树编号为 i 的节点位置一致
- 大根堆:根节点的值大于或等于子节点的值
代码
class MaxHeap {
constructor () {
this.heap = []
this.size = 0
}
swap (a, b) {
const tmp = this.heap[a]
this.heap[a] = this.heap[b]
this.heap[b] = tmp
}
getParentIndex (index) {
return index - 1 >> 1
}
shiftUp (index) {
const parentIndex = this.getParentIndex(index)
if (this.heap[parentIndex] < this.heap[index]) {
this.swap(parentIndex, index)
this.shiftUp(parentIndex)
}
}
getLeftIndex (index) {
return (index << 1) + 1
}
getRightIndex (index) {
return (index << 1) + 2
}
shiftDown (index) {
const leftIndex = this.getLeftIndex(index), rightIndex = this.getRightIndex(index)
if (this.heap[leftIndex] > this.heap[index]) {
this.swap(leftIndex, index)
this.shiftDown(leftIndex)
}
if (this.heap[rightIndex] > this.heap[index]) {
this.swap(rightIndex, index)
this.shiftDown(rightIndex)
}
}
push (value) {
this.heap.push(value)
this.shiftUp(this.size++)
}
top () {
return this.heap[0]
}
pop () {
if (this.size === 0) return null
if (--this.size === 0) return this.heap.pop()
const top = this.top()
this.heap[0] = this.heap.pop()
this.shiftDown(0)
return top
}
isEmpty() {
return this.size === 0
}
}
测试
const maxHeap = new MaxHeap()
for (const a of [3,5,2,4,1]) maxHeap.push(a)
while (!maxHeap.isEmpty()) console.log(maxHeap.pop())
// 5, 4, 3, 2, 1