C语言实现Priority Queue时出队元素打印错误问题排查

我用C语言实现优先队列，预期按Student ID从高到低排序，但出队时打印的studentID错误，尽管Min-Heap数组更新是正确的。

实际输出 #

Original Array: 4 2 6 1 5 3 7 
Dequeued student: 2
Min-Heap array: 2 5 6 1 7 3 
Dequeued student: 5
Min-Heap array: 5 1 6 3 7 
Dequeued student: 6
Min-Heap array: 6 1 7 3 
Min-Heap array: 6 1 7 3  

预期输出 #

Original Array: 4 2 6 1 5 3 7 
Dequeued student: 4 <--
Min-Heap array: 2 5 6 1 7 3 
Dequeued student: 2 <--
Min-Heap array: 5 1 6 3 7 
Dequeued student: 5 <--
Min-Heap array: 6 1 7 3 
Min-Heap array: 6 1 7 3 

问题根源 #

1. dequeue指针错误：当前dequeue返回堆数组第一个元素的指针，但deleteRoot会修改该位置的元素，导致后续打印的是修改后的值，而非出队的原始元素。
2. 堆化逻辑不符需求：现有代码按「最低grade+最低ID」构建Min-Heap，但需求是按「student ID从高到低」排序，比较规则完全错误。

修复方案 #

1. 修正dequeue函数：保存出队元素再返回 #

不能直接返回堆内元素的指针，需先复制出队的根节点元素，再执行删除操作，返回复制后的元素值。

2. 修正堆化逻辑：按Student ID从高到低构建Max-Heap #

把Min-Heap改为Max-Heap，比较规则改为：studentID越大，优先级越高。

完整修复代码 #

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

struct Student;
struct PriorityQueue;

void swap(struct Student *a, struct Student *b);
void heapify(struct PriorityQueue *pq, int size, int i);
void insert(struct PriorityQueue *pq, struct Student *newStudent);
void deleteRoot(struct PriorityQueue *pq);
void printArray(struct PriorityQueue *pq);
struct Student peek(struct PriorityQueue *pq);

struct Student {
    int studentID;
    int grade;
};

struct PriorityQueue {
    struct Student studentPQ[100];
    int size;
};

void swap(struct Student *a, struct Student *b) {
    struct Student temp = *b;
    *b = *a;
    *a = temp;
}

// 堆化：按Student ID从高到低构建Max-Heap
void heapify(struct PriorityQueue *pq, int size, int i) {
    if (size == 1) {
        return;
    }
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 左子节点ID更大，优先级更高
    if (left < size && pq->studentPQ[left].studentID > pq->studentPQ[largest].studentID) {
        largest = left;
    }

    // 右子节点ID更大，优先级更高
    if (right < size && pq->studentPQ[right].studentID > pq->studentPQ[largest].studentID) {
        largest = right;
    }

    // 交换并递归堆化
    if (largest != i) {
        swap(&pq->studentPQ[i], &pq->studentPQ[largest]);
        heapify(pq, size, largest);
    }
}

// 插入元素
void insert(struct PriorityQueue *pq, struct Student *newStudent) {
    if (pq->size == 0) {
        pq->studentPQ[0] = *newStudent;
        pq->size += 1;
    } else {
        pq->studentPQ[pq->size] = *newStudent;
        pq->size += 1;
        // 从最后一个非叶子节点开始堆化
        for (int i = pq->size / 2 - 1; i >= 0; i--) {
            heapify(pq, pq->size, i);
        }
    }
}

// 删除根节点（最高优先级元素）
void deleteRoot(struct PriorityQueue *pq) {
    // 交换根节点和最后一个元素
    swap(&pq->studentPQ[0], &pq->studentPQ[pq->size - 1]);
    pq->size -= 1;
    // 从根节点开始堆化
    heapify(pq, pq->size, 0);
}

// 打印堆数组
void printArray(struct PriorityQueue *pq) {
    for (int i = 0; i < pq->size; ++i)
        printf("%d ", pq->studentPQ[i].studentID);
    printf("\n");
}

// 获取最高优先级元素（不删除）
struct Student peek(struct PriorityQueue *pq) {
    return pq->studentPQ[0];
}

// 出队最高优先级元素
struct Student dequeue(struct PriorityQueue *pq) {
    struct Student removed = pq->studentPQ[0];
    deleteRoot(pq);
    return removed;
}

// 主函数
int main() {
    struct PriorityQueue *pq = (struct PriorityQueue *)malloc(sizeof(struct PriorityQueue));
    pq->size = 0;
    struct Student student1 = {1, 8};
    struct Student student2 = {2, 2};
    struct Student student3 = {3, 9};
    struct Student student4 = {4, 0};
    struct Student student5 = {5, 5};
    struct Student student6 = {6, 6};
    struct Student student7 = {7, 8};

    insert(pq, &student1);
    insert(pq, &student2);
    insert(pq, &student3);
    insert(pq, &student4);
    insert(pq, &student5);
    insert(pq, &student6);
    insert(pq, &student7);

    printf("Original Array: ");
    printArray(pq);

    struct Student dequeueStudent = dequeue(pq);
    printf("Dequeued Student: %d\n", dequeueStudent.studentID);
    printf("Min-Heap array: ");
    printArray(pq);
    
    dequeueStudent = dequeue(pq);
    printf("Dequeued Student: %d\n", dequeueStudent.studentID);
    printf("Min-Heap array: ");
    printArray(pq);

    dequeueStudent = dequeue(pq);
    printf("Dequeued Student: %d\n", dequeueStudent.studentID);
    printf("Min-Heap array: ");
    printArray(pq);

    printf("Min-Heap array: ");
    printArray(pq);

    free(pq);
    return 0;
}

修复说明 #

1. dequeue函数：改为返回结构体值而非指针，先保存根节点元素再执行删除，确保打印的是出队的原始值。
2. 堆化逻辑：将Min-Heap改为Max-Heap，比较条件改为studentID更大的节点优先级更高，符合需求。
3. deleteRoot函数：简化逻辑，直接交换根和最后一个元素，无需遍历查找（因为删除的总是根节点）。

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