嘿,我试着用javascript实现一个最小堆,但是我有一个关于remove m in算法的问题,我使用一个数组在内部表示堆当我向下渗透时,停止的条件应该是什么?在我的代码中,它的大小是2*k
this.removeMin = function () {
//replace root with last element and percolate downwards
var min = this._heap[1],
k,
left,
right;
this._heap[1] = this._heap.pop();
this.size--;
k = 1;
while ( ( 2 * k ) <= this.size) {
left = 2 * k;
right = 2 * k + 1;
if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
if (this._heap[left] <= this._heap[right]) {
swap(this._heap, k, left);
k = left;
} else {
swap(this._heap, k, right);
k = right;
}
} else if (this._heap[k] > this._heap[left]) {
swap(this._heap, k, left);
k = left;
} else {
swap(this._heap, k, right);
k = right;
}
}
return min;
};
最佳答案
我想如果条件允许的话你会错过的当k元素同时小于右和左时,向下必须停止。
必须是:
if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
if (this._heap[left] <= this._heap[right]) {
swap(this._heap, k, left);
k = left;
} else {
swap(this._heap, k, right);
k = right;
}
} else if (this._heap[k] > this._heap[left]) {
swap(this._heap, k, left);
k = left;
} else if(this._heap[k] < this._heap[right]) {
swap(this._heap, k, right);
k = right;
}else{
break;
}
关于javascript - javascript中的最小堆,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35978242/