C语言优先队列实现：详解堆排序代码

本文将带您深入理解如何使用C语言实现优先队列，并通过对代码的逐行解读，帮助您掌握利用堆排序算法维护队列元素优先级的方法。

#include <stdio.h>
#include <string.h>

struct queue{
    char name[11];
    int lev;
};

int n = 0;
struct queue que[100020];

void swap(int x,int y)
{
    struct queue t = que[x];
    que[x] = que[y];
    que[y] = t;
}

void up(int i)
{
    while(i != 1)
    { 
        if(que[i].lev < que[i/2].lev)
            i = i/2;
        else
            return ;
    }
}

void down(int i)
{
    int t = i;
    while(i*2 <= n)
    {
        if(que[t].lev > que[i*2].lev)
            t = i*2;
        
        if(i*2 + 1<=n && que[t].lev > que[i*2+1].lev)
            t = i*2 + 1;
        
        if(t != i)
            swap(t,i);
        else
            return ;
        i = t;
    }
}

int main()
{
    int m;
    scanf('%d',&m);
    int i;
    for(i=0;i<m;i++)
    {
        char s[4];
        scanf('%s',s);
        if(strcmp(s,'PUT') == 0)
        {
            int lv;
            char s[11];
            scanf('%s %d',s,&lv);
            strcpy(que[++n].name,s);
            que[n].lev = lv;
            up(n);
        }
        else
        {
            if(n == 0)
                printf('EMPTY QUEUE!
');
            else
            {
                printf('%s\n',que[1].name);
                swap(1,n);
                n--;//删除第一位
                down(1);
            }
        }
    }
    return 0;
}

代码解析

结构体定义: struct queue 用于表示队列中的元素，包含 name (元素名称) 和 lev (优先级)。
全局变量: n 表示队列大小，que 数组存储队列元素。
swap 函数: 交换队列中两个元素的位置。
up 函数: 将指定位置的元素向上调整，维护堆的性质。
down 函数: 将指定位置的元素向下调整，维护堆的性质。
main 函数:
- 读取操作指令 ('PUT' 或其他)。
- 若为 'PUT'，则读取元素名称和优先级，将其加入队列，并调用 up 函数维护堆。
- 若非 'PUT'，则判断队列是否为空。
  - 若为空，输出 'EMPTY QUEUE!'。
  - 若非空，输出优先级最高的元素 (即 que[1])，将其与队尾元素交换，删除队尾元素，并调用 down 函数维护堆。

这段代码清晰地展示了如何利用堆排序算法实现优先队列。up 和 down 函数是维护堆结构的关键，确保每次操作后堆的性质都能得到维护，从而保证队首元素始终是优先级最高的元素。