如何用C语言实现基于二叉堆、存储结构体的优先队列？

作业背景 #

作业要求用二叉堆实现优先队列：

• 输入规则：第一行是事件总数，第二行是事件序列。非0值表示添加对应优先级的任务（任务编号按顺序递增），0表示移除优先级最高的任务（优先级相同时移除最早加入的）
• 输出要求：输出被移除任务的编号

遇到的问题及错误代码分析 #

1. 结构体赋值错误 #

最初代码中结构体成员赋值写法错误，导致编译失败：

#include <stdio.h>

struct zadanie
{
 int nr;
 int priorytet;
 };

int main()
{
int events;
scanf("%d", &events);

int n = 1;

for (int i=0; i<events; i++)
{
    int x;
    scanf("%d", &x);
    if (x != 0)
    {
        struct zadanie tmp;
        &tmp.nr = n;  // 错误：不能给成员的地址直接赋值
        &tmp.priorytet = x;  // 错误：赋值逻辑颠倒
        n += 1;
    }
}
}

错误原因：&tmp.nr是取成员nr的内存地址，不能直接给地址赋值。正确写法是直接给成员变量赋值：

tmp.nr = n;
tmp.priorytet = x;

2. 堆化函数参数类型不匹配 #

修正赋值逻辑后，又出现request for member ‘priorytet’ in something not a structure or union错误，核心问题在堆化函数的参数定义：

#include <stdio.h>

int size = 0;

struct zadanie
{
 int nr;
 int priorytet;
};

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

// 错误：参数heap被声明为int数组，实际传入的是结构体数组
void kopcenie(int heap[], int size, int i)
{
if (size == 1){
    return;
}
else
{
    int max = i;
    int l = 2*i;
    int p = 2*i+1;
    // 错误：int数组无法访问结构体成员priorytet
    if (l < size && heap[l].priorytet > heap[max].priorytet)
        max = l;
    if (p < size && heap[p].priorytet > heap[max].priorytet)
        max = p;
    if (max != i) 
    {
        // 错误：swap函数接收int指针，但heap元素是结构体
        swap(&heap[i], &heap[max]);
        kopcenie(heap, size, max);
    }
}
}

int main()
{
int events;
scanf("%d", &events);

struct zadanie heap[events];

int n = 1;

for (int i=0; i<events; i++)
{
    int x;
    scanf("%d", &x);
    if (x != 0)
    {
        struct zadanie tmp;
        tmp.nr = n;
        tmp.priorytet = x;
        heap[n] = tmp;
        n += 1;
        
    }
}
}

错误原因：

• 堆化函数kopcenie的参数heap被声明为int[]，与实际传入的struct zadanie数组类型不匹配，导致无法访问结构体成员。
• swap函数仅支持int类型交换，无法处理结构体变量的交换。
• 全局size变量未随任务添加更新，堆的大小管理缺失。
• 未处理优先级相同的情况：作业要求优先级相同时移除最早加入的任务，需要在堆化比较中加入任务编号的判断。

关键修正点 #

1. 修正堆化函数参数类型：
   将堆化函数的参数改为结构体数组：

void kopcenie(struct zadanie heap[], int size, int i)

2. 修改swap函数支持结构体交换：

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

3. 完善堆化比较逻辑：
   当优先级相同时，任务编号越小（加入越早）优先级越高，调整比较条件：

// 左子节点优先级更高，或优先级相同但编号更小
if (l < size && (heap[l].priorytet > heap[max].priorytet || 
    (heap[l].priorytet == heap[max].priorytet && heap[l].nr < heap[max].nr)))
    max = l;
// 右子节点同理
if (p < size && (heap[p].priorytet > heap[max].priorytet || 
    (heap[p].priorytet == heap[max].priorytet && heap[p].nr < heap[max].nr)))
    max = p;

4. 维护堆的大小与结构：
   添加任务时更新堆大小并执行向上堆化，保证堆结构正确：

// 添加任务时
heap[size] = tmp;
size++;
// 向上堆化，修复堆结构
for (int j = size-1; j > 0 && (heap[j].priorytet > heap[(j-1)/2].priorytet || 
    (heap[j].priorytet == heap[(j-1)/2].priorytet && heap[j].nr < heap[(j-1)/2].nr)); 
    j = (j-1)/2) {
    swap(&heap[j], &heap[(j-1)/2]);
}

5. 实现移除堆顶操作：
   遇到输入0时，移除堆顶元素（优先级最高的任务），输出其编号后调整堆结构：

else {
    if (size == 0) return;  // 堆为空时跳过
    printf("%d\n", heap[0].nr);  // 假设堆从索引0开始
    heap[0] = heap[size-1];
    size--;
    kopcenie(heap, size, 0);
}

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