Возникли проблемы с удалением в моей реализации Binary Heap / Priority Queue

Question

Я пытаюсь реализовать метод удаления для моей реализации двоичной кучи.

class Node {
  constructor(priority) {
    this.priority = priority;
  }
}

class PriorityQueue {
  constructor() {
    this.heap = [null];
  }

remove() {

  const toRemove = this.heap[1];
  this.heap[1] = this.heap.pop();  
  let currentIdx = 1;
  let [left, right] = [2*currentIdx, 2*currentIdx + 1]; 
  let currentChildIdx = this.heap[right] && this.heap[right].priority >= this.heap[left].priority ? right : left; //Assess which child node has higher priority

  while (this.heap[currentChildIdx] && this.heap[currentIdx].priority <= this.heap[currentChildIdx].priority) { 
    let currentNode = this.heap[currentIdx]
    let currentChildNode = this.heap[currentChildIdx];
    this.heap[currentChildIdx] = currentNode;
    this.heap[currentIdx] = currentChildNode;
    currentIdx = this.heap.indexOf(currentNode);
  }
  return toRemove;
}


}

Однако я не уверен, как правильно обновлять значения currentIdx и currentChildIdx, когда я запускаю свой while l oop. На самом деле код перестает работать, когда я пытаюсь обновить значение currentIdx

currentIdx = this.heap.indexOf(currentNode);

Любые советы о том, что я делаю неправильно?

Полный код здесь: https://repl.it/@Stylebender / Binary-Heap-Наивный

Answer 1

В l oop, как только вы поменяете местами значения для currentIdx и currentChildIdx, вам следует присвоить currentIdx = currentChildIdx.

. И как только вы измените currentIdx, вам нужно будет повторно вычислить левый и правый дочерние индексы и новая currentChildIdx.

Основная идея c заключается в следующем:

while currentIdx < heap_length
    currentChildIdx = index of largest child
    if (heap[currentIdx] >= heap[currentChildIdx])
        break; // node is now in the right place
    swap(heapCurrentIdx, heap[currentChildIdx)
    currentIdx = currentChildIdx

Я предлагаю вам построить эту базовую c структуру и затем выполните один шаг в отладчике, чтобы убедиться, что он работает должным образом.