时间戳

首页 > 解决方案 > 在我的二进制堆/优先级队列实现中实现删除时遇到问题

data-structures - 在我的二进制堆/优先级队列实现中实现删除时遇到问题

问题描述

我正在尝试为我的二进制堆实现实现删除方法。

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


}

但是，我不确定在运行 while 循环时如何正确更新 currentIdx 和 currentChildIdx 的值。事实上，当我尝试更新 currentIdx 的值时，代码似乎停止工作

currentIdx = this.heap.indexOf(currentNode);

关于我做错了什么的任何提示？

完整代码在这里：https ://repl.it/@Stylebender/Binary-Heap-Naive

标签： data-structurespriority-queuebinary-heap

解决方案

在循环中，一旦你交换了 and 的值currentIdx，currentChildIdx那么你应该分配currentIdx = currentChildIdx.

而一旦你改变currentIdx了，你需要重新计算左右子索引和一个新的currentChildIdx.

基本思想是：

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

我的建议是您构建该基本结构，然后在调试器中单步执行它以确保它按预期工作。

推荐阅读