当前位置：首页 > C > 正文

C语言优先队列详解（从零开始手把手教你用堆实现优先队列）

主机测评网
C
2025-12-15
409

在计算机科学中，优先队列是一种非常重要的数据结构。与普通队列“先进先出”不同，优先队列总是弹出当前优先级最高的元素。在C语言中，我们通常使用堆（Heap）来高效地实现优先队列。

本文将带你从零开始，用C语言一步步实现一个基于最大堆的优先队列。即使你是编程小白，也能轻松理解并掌握C语言优先队列的核心思想和代码实现。

什么是优先队列？

优先队列是一种抽象数据类型，支持以下基本操作：

push：插入一个元素
pop：删除并返回优先级最高的元素
top：查看优先级最高的元素（不删除）
size：获取队列中元素个数
empty：判断队列是否为空

C语言优先队列详解（从零开始手把手教你用堆实现优先队列） C语言优先队列优先队列实现 C语言数据结构堆实现优先队列第1张

为什么用堆实现优先队列？

堆是一种特殊的完全二叉树，具有以下性质：

最大堆：每个父节点的值 ≥ 其子节点的值
最小堆：每个父节点的值 ≤ 其子节点的值

利用堆的性质，我们可以在 O(log n) 时间内完成插入和删除操作，非常适合实现高效的优先队列实现。

C语言优先队列完整实现

下面我们用C语言实现一个基于最大堆的优先队列。我们将使用数组来模拟堆结构。

#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 1000typedef struct {    int data[MAX_SIZE];    int size;} PriorityQueue;// 初始化优先队列void init(PriorityQueue* pq) {    pq->size = 0;}// 获取父节点索引int parent(int i) {    return (i - 1) / 2;}// 获取左子节点索引int left_child(int i) {    return 2 * i + 1;}// 获取右子节点索引int right_child(int i) {    return 2 * i + 2;}// 上浮操作：维护堆性质void sift_up(PriorityQueue* pq, int i) {    if (i == 0) return;        int p = parent(i);    if (pq->data[i] > pq->data[p]) {        // 交换        int temp = pq->data[i];        pq->data[i] = pq->data[p];        pq->data[p] = temp;                // 递归上浮        sift_up(pq, p);    }}// 下沉操作：维护堆性质void sift_down(PriorityQueue* pq, int i) {    int max_index = i;    int l = left_child(i);    int r = right_child(i);        // 找到最大值的索引    if (l < pq->size && pq->data[l] > pq->data[max_index])        max_index = l;        if (r < pq->size && pq->data[r] > pq->data[max_index])        max_index = r;        // 如果最大值不是当前节点，则交换并继续下沉    if (max_index != i) {        int temp = pq->data[i];        pq->data[i] = pq->data[max_index];        pq->data[max_index] = temp;                sift_down(pq, max_index);    }}// 插入元素void push(PriorityQueue* pq, int value) {    if (pq->size == MAX_SIZE) {        printf("Priority queue is full!\n");        return;    }        pq->data[pq->size] = value;    sift_up(pq, pq->size);    pq->size++;}// 弹出最大元素int pop(PriorityQueue* pq) {    if (pq->size == 0) {        printf("Priority queue is empty!\n");        return -1; // 或者使用错误处理机制    }        int result = pq->data[0];    pq->size--;    pq->data[0] = pq->data[pq->size];    sift_down(pq, 0);        return result;}// 查看最大元素int top(PriorityQueue* pq) {    if (pq->size == 0) {        printf("Priority queue is empty!\n");        return -1;    }    return pq->data[0];}// 判断是否为空int empty(PriorityQueue* pq) {    return pq->size == 0;}// 获取大小int size(PriorityQueue* pq) {    return pq->size;}// 测试函数int main() {    PriorityQueue pq;    init(&pq);        push(&pq, 10);    push(&pq, 30);    push(&pq, 20);    push(&pq, 5);        printf("Top element: %d\n", top(&pq)); // 输出 30        while (!empty(&pq)) {        printf("Popped: %d\n", pop(&pq));    }        return 0;}