JavaScript最小优先队列dequeue报错：无法读取undefined的priority属性

问题描述 #

我用JavaScript实现了一个最小优先队列，但dequeue方法无法正常工作。控制台报错：TypeError: Cannot read properties of undefined (reading 'priority')。我能正常插入所有节点到数组，执行dequeue后数组的节点数量是对的，但第一次取出oldNode后，后续调用无法再返回正确的oldNode。

原始代码 #

//min-heap
class PriorityQueue {
  constructor(){
    this.values = [];
  }
  enqueue(value, priority){
    let newNode = new Node(value, priority);
    this.values.push(newNode);
    this.bubbleUp();
  }
  bubbleUp(){
    let childIndex = this.values.length - 1;
    let parentIndex = Math.floor((childIndex - 1) / 2);

    while(childIndex > 0 && this.values[childIndex].priority < this.values[parentIndex].priority){
      let temp = this.values[childIndex];
      this.values[childIndex] = this.values[parentIndex];
      this.values[parentIndex] = temp;

      childIndex = parentIndex;
      parentIndex = Math.floor((childIndex - 1) / 2);
    }
  }
  dequeue(){
    if(!this.values.length) return null;
    //swap root and highest number element
    this.swap(0, this.values.length - 1);
    let oldNode = this.values.pop();

    let parent = 0, childLeft = 1, childRight = 2;
    let min = Math.min(this.values[childLeft].priority, this.values[childRight].priority);

    while(this.values[parent].priority > min){
      let child = this.values[childLeft].priority === min ? childLeft : childRight;
      this.swap(parent, child);
      parent = child;

      //get children of current parent
      childLeft = parent * 2 + 1;
      childRight = parent * 2 + 2;

      min = Math.min(this.values[childLeft].priority, this.values[childRight].priority);
    }
    return oldNode;
  }
  swap(index1, index2){
    [this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]];
  }
}

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

错误原因 #

1. 子节点越界未处理：当堆中剩余元素少于2个时，childLeft或childRight会超出数组长度，导致this.values[childLeft]或this.values[childRight]为undefined，读取priority属性时直接抛出TypeError。
2. 循环条件不严谨：原代码没有判断子节点是否存在，即使父节点已经是叶子节点，循环仍会尝试比较不存在的子节点优先级，导致错误。

修复后的代码 #

//min-heap
class PriorityQueue {
  constructor(){
    this.values = [];
  }
  enqueue(value, priority){
    let newNode = new Node(value, priority);
    this.values.push(newNode);
    this.bubbleUp();
  }
  bubbleUp(){
    let childIndex = this.values.length - 1;
    let parentIndex = Math.floor((childIndex - 1) / 2);

    while(childIndex > 0 && this.values[childIndex].priority < this.values[parentIndex].priority){
      let temp = this.values[childIndex];
      this.values[childIndex] = this.values[parentIndex];
      this.values[parentIndex] = temp;

      childIndex = parentIndex;
      parentIndex = Math.floor((childIndex - 1) / 2);
    }
  }
  dequeue(){
    if(!this.values.length) return null;
    // 交换根节点和最后一个节点
    this.swap(0, this.values.length - 1);
    let oldNode = this.values.pop();
    
    // 如果堆中只剩0或1个元素，直接返回
    if(this.values.length <= 1) return oldNode;

    let parent = 0;
    const length = this.values.length;

    while(true){
      let childLeft = parent * 2 + 1;
      let childRight = parent * 2 + 2;
      let swapIndex = null;

      // 左子节点存在且优先级小于父节点
      if(childLeft < length && this.values[childLeft].priority < this.values[parent].priority){
        swapIndex = childLeft;
      }
      // 右子节点存在：如果左子节点不存在且右子节点优先级小，或者右子节点优先级比左子节点更小
      if(childRight < length){
        if(
          (swapIndex === null && this.values[childRight].priority < this.values[parent].priority) ||
          (swapIndex !== null && this.values[childRight].priority < this.values[childLeft].priority)
        ){
          swapIndex = childRight;
        }
      }

      // 没有需要交换的子节点，退出循环
      if(swapIndex === null) break;

      // 交换父节点和优先级最小的子节点
      this.swap(parent, swapIndex);
      parent = swapIndex;
    }
    return oldNode;
  }
  swap(index1, index2){
    [this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]];
  }
}

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

关键修改点 #

1. 子节点存在性检查：每次获取子节点索引后，先判断是否小于数组长度，确保不会访问undefined元素。
2. 动态确定交换目标：通过swapIndex记录需要交换的子节点，只有当子节点优先级确实小于父节点时才标记交换，避免无效操作。
3. 循环终止条件：当没有需要交换的子节点时（swapIndex === null），直接退出循环，避免无意义的计算。
4. 边界情况处理：弹出根节点后，如果堆中剩余元素≤1，直接返回，不需要执行下沉逻辑。

内容的提问来源于stack exchange，提问作者AlmostThere