最小索引堆
由于最小堆存在以下问题：
- 如果数据非常大的情况下，堆中交换元素会消耗大部分的时间
- 位置改变后，查询元素会变得困难
所以需要通过索引堆来实现，实现之后，现在不是直接交换堆中的元素，而是增加多一个 index 堆，直接对于索引执行操作
代码实现
const MinHeap = require('./min-heap');
class IndexMinHeap {
constructor() {
this.data = [];
this.index = [];
this.count = 0;
}
getParentIndex(i) {
return i >> 1;
}
getLeftChildIndex(i) {
return 2 * i + 1;
}
getRightChildIndex(i) {
return 2 * i + 2;
}
swap(i, j) {
const temp = this.index[i];
this.index[i] = this.index[j];
this.index[j] = temp;
}
insert(item) {
this.count++;
this.data[this.count] = item;
this.index[this.count] = this.count;
this.shiftUp(this.count);
}
shiftUp(i) {
while (i >= 1) {
const parentIndex = this.getParentIndex(i);
if (this.data[this.index[parentIndex]] > this.data[this.index[i]]) {
this.swap(parentIndex, i);
this.shiftUp(parentIndex);
} else {
break;
}
}
}
shiftDown(i) {
while (2 * i <= this.count) {
const leftChildIndex = this.getLeftChildIndex();
const rightChildIndex = this.getRightChildIndex();
let minIndex = leftChildIndex;
if (this.data[this.index[leftChildIndex]] > this.data[this.index[rightChildIndex]]) {
minIndex = rightChildIndex;
}
if (this.data[this.index[i]] > this.data[this.index[minIndex]]) {
this.swap(i, minIndex);
this.shiftDown(minIndex);
} else {
break;
}
}
}
extraMin() {
const head = this.data[this.index[1]];
this.index[1] = this.index.pop();
this.count--;
this.shiftDown(1);
return head;
}
getMin() {
return this.data[this.index[1]];
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
}
const indexMinHeap = new IndexMinHeap();
indexMinHeap.insert(9);
indexMinHeap.insert(11);
indexMinHeap.insert(5);
console.log(indexMinHeap.data);
console.log(indexMinHeap.index);
console.log(indexMinHeap.extraMin());
indexMinHeap.insert(8);
console.log(indexMinHeap.extraMin());
indexMinHeap.insert(3);
console.log(indexMinHeap.extraMin());
// arr 3 2 1
// index 3 1 2
// 0 1 2 3