JS手写最小堆（小顶堆）、最大堆（大顶堆）
最编程
2023-12-31 14:45:16
...
let heap = [];
function swap(index1, index2) {
[heap[index1], heap[index2]] = [heap[index2], heap[index1]]
}
function shiftup(index) {
let parentIndex = Math.floor((index - 1) / 2);
if (index != 0 && heap[parentIndex] > heap[index]) {
swap(parentIndex, index);
shiftup(parentIndex);
}
}
function shiftDown(index) {
let leftNodeIndex = (index + 1) * 2 - 1, rightNodeIndex = (index + 1) * 2
if (leftNodeIndex < heap.length && heap[leftNodeIndex] < heap[index]) {
swap(leftNodeIndex, index);
shiftDown(leftNodeIndex);
}
if (rightNodeIndex < heap.length && heap[rightNodeIndex] < heap[index]) {
swap(rightNodeIndex, index);
shiftDown(rightNodeIndex);
}
}
function insert(val) {
heap.push(val);
shiftup(heap.length - 1);
}
function remove() {
swap(0, heap.length - 1);
let temp = heap.pop();
shiftDown(0);
return temp;
}
上一篇： 大顶堆的实现（基于数组存储的完全二叉树）
下一篇： 堆排序中的大顶堆和小顶堆