二叉最小堆实现优先队列：插入函数异常问题求助

你的代码存在三个核心问题，直接导致插入后堆结构不符合最小堆要求：

1. 插入函数父节点索引计算错误 #

你的堆采用1-based索引（deleteMin从arr[1]取最小值、printQueue从i=1开始遍历），但插入时误用了0-based的父节点计算公式parent=(index-1)/2，这会让新节点错误地和索引0的初始化值比较，而非堆的实际父节点。

正确的1-based父节点计算公式为：parent = index / 2（整数除法），比如索引2、3的父节点都是1，而非0。

2. 下沉调整函数未递归处理 #

当前percolateDown仅交换一次就终止，没有对交换后的新位置继续做下沉调整，无法完全修正堆结构。需要在交换后递归调用percolateDown处理新的节点位置。

3. 构造函数数组初始化越界 #

构造函数中循环条件i <= arrSize会访问arr[arrSize]，但数组是new int[arrSize]，合法索引范围是0到arrSize-1，越界会引发未定义行为。

修正后的完整代码 #

#include "PriorityQueue.hpp"
#include <iostream>

using namespace std;

PriorityQueue::PriorityQueue():arrSize(100), currentSize(0){
  arr = new int[arrSize];
  // 修正：避免数组越界
  for(int i = 0; i < arrSize; i++){
    arr[i] = 0;
  }
}

bool PriorityQueue::isEmpty(){
  return currentSize == 0;
}

void PriorityQueue::insert(int value){
  currentSize++;
  int index = currentSize;
  arr[index] = value;
  // 修正：1-based父节点计算
  int parent = index / 2;
  // 循环条件改为index>1，根节点无父节点
  while(index > 1 && arr[parent] > arr[index]){
    swap(arr[index], arr[parent]);
    index = parent;
    parent = index / 2;
  }
}

int PriorityQueue::deleteMin(){
  int min = arr[1];
  arr[1] = arr[currentSize];
  currentSize--;
  percolateDown(1);
  return min;
}

void PriorityQueue::printQueue(){
  for (int i = 1; i <= currentSize; i++){
    cout << arr[i] << " ";
  }
  cout << endl;
}

void PriorityQueue::percolateDown(int hole){
  int minIndex = hole;
  int left = 2 * hole;
  int right = 2 * hole + 1;

  if (left <= currentSize && arr[left] < arr[minIndex]){
    minIndex = left;
  }

  if (right <= currentSize && arr[right] < arr[minIndex]){
    minIndex = right;
  }

  if(minIndex != hole){
    swap(arr[hole], arr[minIndex]);
    // 修正：递归处理交换后的新位置
    percolateDown(minIndex);
  }
}

测试验证 #

插入序列100 70 50 125 45 60 10后，printQueue的输出会变为预期的：

10 45 50 125 100 70 60

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