在JavaScript中的最小堆

Question

嘿我試圖在JavaScript中實現一個小堆，但我有一個關於刪除最小的算法的問題。我使用數組來表示堆內部。當我向下滲透時，停止條件應該是什麼？在我的代碼中，我使用了2 * k < = this.size，所以它可能會傳遞到最後一個元素，但它不會覺得「正確」，是否有更好的停止條件？提前致謝！

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; 
}; 

Answer 1

我想你錯過了一個條件。當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; 
    }