切换主题
二叉堆
二叉堆（是完全二叉树结构，二叉堆又叫优先级队列）要么是大顶堆，要么是小顶堆！
首先用数组A来定义二叉堆，对该数组每项i有:
- 它的左侧子节点的下标:
idxL = 2 * i + 1（如果位置可用） - 它的右侧子节点的下标:
idxR = 2 * i + 2（如果位置可用） - 它的父节点的下标:
idxP = (i - 1) >> 1（如果位置可用） - 第一个非叶节点下标：
idx = (A.length >> 1) - 1 - 大顶堆：
A[i] >= A[2i+1] && A[i] >= A[2i+2] - 小顶堆：
A[i] <= A[2i+1] && A[i] <= A[2i+2]
代码实现
JavaScript
class BinaryHeap {
constructor(comparator = (a, b) => a - b) {
this.A = []
this.comp = comparator
}
size() {
return this.A.length
}
peek() {
if (!this.size()) {
throw '堆为空'
}
return this.A[0]
}
add(val) {
this.A.push(val) // 将值插入堆的底部叶节点，即数组末位
this.siftUp()
}
poll() {
const [top, end] = [this.peek(), this.A.pop()]
if (this.size()) {
this.A[0] = end
this.siftDown()
}
return top
}
// heapInsert
siftUp() {
// 将新插入的值和它的父节点进行交换，直到父节点大于这个值
let [idx, idxP] = [this.size() - 1, (idx - 1) >> 1]
while (idx > 0 && this.comp(this.A[idx], this.A[idxP]) > 0) {
[this.A[idx], this.A[idxP]] = [this.A[idxP], this.A[idx]]
[idx, idxP] = [idxP, (idx - 1) >> 1]
}
}
// heapify
siftDown() {
const [i, len] = [0, this.size()];
for (let j = i * 2 + 1; i < len; i = 2 * j + 1) {
if (j + 1 < len && this.comp(this.A[j + 1], this.A[j]) > 0) {
j++
}
if (this.comp(this.A[j], this.A[i]) > 0) {
[this.A[i], this.A[j]] = [this.A[j], this.A[i]]
i = j
} else {
break
}
}
}
}