最小堆特点是一棵完全二叉树，父节点小于子节点；采用数组存储。
代码详情
function push(heap, node) {
const index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}
function peek(heap) {
return heap.length === 0 ? null : heap[0];
}
function pop(heap) {
if (heap.length === 0) {
return null;
}
const first = heap[0];
const last = heap.pop();
if (last !== first) {
heap[0] = last;
siftDown(heap, last, 0);
}
return first;
}
function siftUp(heap, node, i) {
let index = i;
while (index > 0) {
const parentIndex = (index - 1) >>> 1;
const parent = heap[parentIndex];
if (compare(parent, node) > 0) {
heap[parentIndex] = node;
heap[index] = parent;
index = parentIndex;
} else {
return;
}
}
}
function siftDown(heap, node, i) {
let index = i;
const length = heap.length;
const halfLength = length >>> 1;
while (index < halfLength) {
const leftIndex = (index + 1) * 2 - 1;
const left = heap[leftIndex];
const rightIndex = leftIndex + 1;
const right = heap[rightIndex];
if (compare(left, node) < 0) {
if (rightIndex < length && compare(right, left) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
heap[index] = left;
heap[leftIndex] = node;
index = leftIndex;
}
} else if (rightIndex < length && compare(right, node) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
return;
}
}
}
function compare(a, b) {
const diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : a.id - b.id;
}
const heap = [];
let id = 0;
push(heap, { sortIndex: 7, id: id++ });
push(heap, { sortIndex: 2, id: id++ });
push(heap, { sortIndex: 1, id: id++ });
push(heap, { sortIndex: 3, id: id++ });
pop(heap);
console.log(heap);
// heap
// [
// { sortIndex: 2, id: 1 },
// { sortIndex: 3, id: 3 },
// { sortIndex: 7, id: 0 }
// ]
知识点
- 插入节点：将待插入节点放到数组末尾向上调整；
- 删除节点：数组第一个元素是最小节点，将最后一个元素放到最前面，然后向下调整；
