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!\n');
            else
            {
                printf('%s\n',que[1].name);
                swap(1,n);
                n--;//删除第一位
                down(1);
            }
        }
    }
    return 0;
}

代码解释

struct queue: 定义了队列中每个元素的结构，包含 name 和 lev 两个字段，分别表示元素的名称和优先级。
n: 表示队列中元素的数量。
que: 存储优先队列元素的数组。
swap(int x, int y): 交换队列中索引为 x 和 y 的两个元素。
up(int i): 将索引为 i 的元素向上调整，以维护堆的性质。
down(int i): 将索引为 i 的元素向下调整，以维护堆的性质。
main(): 主函数，读取操作指令并进行相应的操作。

算法分析

这段代码使用数组实现了一个最小堆，利用最小堆的性质实现了优先队列的功能。

入队: 将新元素插入到堆的末尾，然后调用 up() 函数将其向上调整，直到满足堆的性质。
出队: 返回堆顶元素（优先级最高的元素），然后将堆的最后一个元素与堆顶元素交换，并将堆的大小减一，最后调用 down() 函数将新的堆顶元素向下调整，直到满足堆的性质。

总结

本篇文章介绍了如何使用C语言实现一个简单的优先队列，并提供了详细的代码解释和示例。优先队列是一种非常有用的数据结构，可以应用于许多不同的场景，例如任务调度、网络路由等。