Min heap in javascript

Question

Эй, я попытался реализовать кучу минут в javascript, но у меня возник вопрос относительно алгоритма удаления min. Я использую массив для представления кучи внутри. Когда я просачиваюсь вниз, каково должно быть условие остановки? В моем коде у меня есть 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; 
    }