这个优先队列使用数组存储。下面的代码是一个最大堆的实现。
class MaxHeap {
constructor() {
this.heapList = [0];
this.heapSize = 0;
}
insert = (value) => {
this.heapList.push(value);
this.heapSize += 1;
this.moveUp(this.heapSize);
};
moveUp = (position) => {
while (Math.floor(position / 2) > 0) {
const parent = Math.floor(position / 2);
if (this.heapList[position][1] > this.heapList[parent][1]) {
const temp = this.heapList[position];
this.heapList[position] = this.heapList[parent];
this.heapList[parent] = temp;
}
position = parent;
}
};
remove = (value) => {
const maxValue = this.heapList[1];
this.heapList[1] = this.heapList[this.heapSize];
this.heapList.pop();
this.heapSize -= 1;
this.moveDown(1);
return maxValue;
};
moveDown = (parentPosition) => {
while (parentPosition * 2 <= this.heapSize) {
const maxChildPosition = this.findMaxChild(parentPosition);
if (this.heapList[maxChildPosition][1] > this.heapList[parentPosition][1]) {
const temp = this.heapList[maxChildPosition];
this.heapList[maxChildPosition] = this.heapList[parentPosition];
this.heapList[parentPosition] = temp;
}
parentPosition = maxChildPosition;
}
};
findMaxChild = (position) => {
const leftChild = position * 2;
const rightChild = position * 2 + 1;
if (rightChild > this.heapSize) {
return leftChild;
} else {
if (this.heapList[rightChild][1] > this.heapList[leftChild][1]) {
return rightChild;
} else {
return leftChild;
}
}
};
build = (arrayList) => {
const len = arrayList.length;
this.heapSize = len;
this.heapList = [0, ...arrayList];
let position = Math.floor(len / 2);
while (position > 0) {
this.moveDown(position);
position -= 1;
}
};
}
《简易优先队列 js 版》有一个想法