最小堆,又称为小根堆,小顶堆,实现 JavaScript 版小根堆的代码。
<=
叶子节点的值class MinHeap {
constructor() {
this.heap = []
this.size = 0
}
swap(i, j) {
const tmp = this.heap[i]
this.heap[i] = this.heap[j]
this.heap[j] = 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)
const 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 tmp = this.heap[0]
this.heap[0] = this.heap.pop()
this.shiftDown(0)
return tmp
}
isEmpty() {
return this.size === 0
}
}
const minHeap = new MinHeap()
for (const a of [3,5,2,4,1]) minHeap.push(a)
while (!minHeap.isEmpty()) console.log(minHeap.pop())
// [1, 2, 3, 4, 5]