大、小根堆
字数
954 字
阅读时间
5 分钟
参考资料：JavaScript大、小根堆 - 掘金
大、小根堆是一种特殊的完全二叉树，它满足堆的性质：
- 大根堆 (Max Heap)：每个节点的值都大于或等于其子节点的值，因此根节点是堆中最大的元素。
- 小根堆 (Min Heap)：每个节点的值都小于或等于其子节点的值，因此根节点是堆中最小的元素。
堆通常用于实现优先队列，其中元素的出队顺序是按照优先级（即元素值的大小）来决定的。
堆的构建与核心操作
堆的核心操作包括 push()（插入元素）和 pop()（删除堆顶元素）。这些操作通过维护堆的性质（上浮 up 和下沉 down）来实现。
以下是一个简化的堆实现示例，其中包含 push 和 pop 的核心逻辑，以及必要的辅助函数。
javascript
class Heap {
constructor(compareFn) {
this.list = [null]; // 数组的第一个元素通常留空，方便计算子节点和父节点索引
this.compare = compareFn || ((a, b) => a - b); // 默认小根堆 (a-b)，大根堆 (b-a)
}
// 获取堆的大小
getSize() {
return this.list.length - 1;
}
// 获取父节点索引
parent(k) {
return Math.floor(k / 2);
}
// 获取左子节点索引
left(k) {
return 2 * k;
}
// 获取右子节点索引
right(k) {
return 2 * k + 1;
}
// 交换两个元素
swap(i, j) {
[this.list[i], this.list[j]] = [this.list[j], this.list[i]];
}
/**
* 元素上浮操作
* 当新插入的元素比父节点大（大根堆）或小（小根堆）时，需要上浮
* @param {number} k 当前元素的索引
*/
up(k) {
const { parent, compare, list, swap } = this;
// 当 k > 1 (不是根节点) 且当前元素比父节点更符合堆的性质时，进行交换
while (k > 1 && compare(list[k], list[parent(k)]) < 0) { // 小根堆：list[k] < list[parent(k)]
swap(k, parent(k));
k = parent(k);
}
}
/**
* 元素下沉操作
* 当堆顶元素被移除或替换后，需要将新堆顶元素下沉以维护堆的性质
* @param {number} k 当前元素的索引
*/
down(k) {
const { left, right, compare, list, swap, getSize } = this;
const size = getSize();
while (left(k) <= size) { // 如果有左子节点
let j = left(k); // 假设左子节点是符合堆性质的子节点
// 如果有右子节点，并且右子节点比左子节点更符合堆的性质，则选择右子节点
if (right(k) <= size && compare(list[right(k)], list[j]) < 0) { // 小根堆：list[right(k)] < list[j]
j = right(k);
}
// 如果当前元素已经比子节点更符合堆的性质，则停止下沉
if (compare(list[k], list[j]) <= 0) { // 小根堆：list[k] <= list[j]
break;
}
// 否则，交换当前元素与选定的子节点，并继续下沉
swap(k, j);
k = j;
}
}
/**
* 插入元素
* @param {*} val 要插入的值
*/
push(val) {
this.list.push(val);
this.up(this.getSize()); // 新元素插入到末尾，然后上浮
}
/**
* 移除并返回堆顶元素
* @returns {*} 堆顶元素
*/
pop() {
const size = this.getSize();
if (size === 0) return null;
this.swap(1, size); // 将堆顶元素与最后一个元素交换
const top = this.list.pop(); // 移除并返回原堆顶元素
this.down(1); // 新的堆顶元素下沉以维护堆的性质
return top;
}
/**
* 查看堆顶元素
* @returns {*} 堆顶元素
*/
peek() {
return this.getSize() > 0 ? this.list[1] : null;
}
}
// 示例：创建一个小根堆
const minHeap = new Heap((a, b) => a - b);
minHeap.push(3);
minHeap.push(1);
minHeap.push(2);
console.log("Min Heap Peek:", minHeap.peek()); // 1
console.log("Min Heap Pop:", minHeap.pop()); // 1
console.log("Min Heap Peek:", minHeap.peek()); // 2
// 示例：创建一个大根堆
const maxHeap = new Heap((a, b) => b - a);
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(2);
console.log("Max Heap Peek:", maxHeap.peek()); // 3
console.log("Max Heap Pop:", maxHeap.pop()); // 3
console.log("Max Heap Peek:", maxHeap.peek()); // 2贡献者
jiechen