C语言优先队列实现（从零开始掌握堆结构构建高效优先队列）

什么是二叉堆？

二叉堆是一种完全二叉树，分为两种类型：

• 最大堆（Max-Heap）：父节点的值 ≥ 子节点的值，根节点为最大值。
• 最小堆（Min-Heep）：父节点的值 ≤ 子节点的值，根节点为最小值。

在本教程中，我们将实现一个最大堆，用于构建高优先级先出的优先队列。

C语言优先队列的基本结构

我们使用数组来模拟堆结构（因为完全二叉树可以用数组高效表示）。以下是我们的优先队列结构体定义：

// 优先队列结构体typedef struct {    int* data;      // 存储堆元素的数组    int size;       // 当前元素个数    int capacity;   // 数组最大容量} PriorityQueue;

核心操作函数

我们需要实现以下几个关键函数：

• createQueue：创建优先队列
• swap：交换两个元素
• heapifyUp：插入后向上调整
• heapifyDown：删除后向下调整
• enqueue：入队（插入元素）
• dequeue：出队（取出最高优先级元素）
• peek：查看最高优先级元素
• destroyQueue：释放内存

1. 创建与销毁

PriorityQueue* createQueue(int capacity) {    PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));    pq->data = (int*)malloc(capacity * sizeof(int));    pq->size = 0;    pq->capacity = capacity;    return pq;}void destroyQueue(PriorityQueue* pq) {    free(pq->data);    free(pq);}

2. 辅助函数：交换与父子节点索引

void swap(int* a, int* b) {    int temp = *a;    *a = *b;    *b = temp;}// 获取父节点索引int parent(int i) { return (i - 1) / 2; }// 获取左子节点索引int leftChild(int i) { return 2 * i + 1; }// 获取右子节点索引int rightChild(int i) { return 2 * i + 2; }

3. 向上调整（插入后）

当新元素插入到堆底时，若它比父节点大，就需要不断上移，直到满足堆性质。

void heapifyUp(PriorityQueue* pq, int index) {    if (index > 0 && pq->data[parent(index)] < pq->data[index]) {        swap(&pq->data[index], &pq->data[parent(index)]);        heapifyUp(pq, parent(index));    }}

4. 向下调整（删除后）

删除根节点后，将最后一个元素移到根，然后向下调整以恢复堆性质。

void heapifyDown(PriorityQueue* pq, int index) {    int largest = index;    int left = leftChild(index);    int right = rightChild(index);    if (left < pq->size && pq->data[left] > pq->data[largest])        largest = left;    if (right < pq->size && pq->data[right] > pq->data[largest])        largest = right;    if (largest != index) {        swap(&pq->data[index], &pq->data[largest]);        heapifyDown(pq, largest);    }}

5. 入队与出队

void enqueue(PriorityQueue* pq, int value) {    if (pq->size == pq->capacity) {        printf("队列已满！\n");        return;    }    pq->data[pq->size] = value;    heapifyUp(pq, pq->size);    pq->size++;}int dequeue(PriorityQueue* pq) {    if (pq->size == 0) {        printf("队列为空！\n");        return -1; // 或抛出错误    }    int root = pq->data[0];    pq->data[0] = pq->data[pq->size - 1];    pq->size--;    heapifyDown(pq, 0);    return root;}int peek(PriorityQueue* pq) {    if (pq->size == 0) {        printf("队列为空！\n");        return -1;    }    return pq->data[0];}

完整示例：测试优先队列

#include <stdio.h>#include <stdlib.h>// 上述所有函数定义...int main() {    PriorityQueue* pq = createQueue(10);    enqueue(pq, 10);    enqueue(pq, 30);    enqueue(pq, 20);    enqueue(pq, 50);    enqueue(pq, 40);    printf("当前最高优先级: %d\n", peek(pq)); // 输出 50    while (pq->size > 0) {        printf("出队: %d\n", dequeue(pq));    }    destroyQueue(pq);    return 0;}

总结

通过本教程，你已经掌握了如何用 C语言实现优先队列。这种基于堆实现优先队列的方法时间复杂度优秀：插入和删除均为 O(log n)，非常适合需要频繁访问最大/最小元素的场景。

无论你是学习 C语言数据结构 的学生，还是准备面试的开发者，理解优先队列的原理和实现都至关重要。希望这篇优先队列C语言教程能为你打下坚实基础！

提示：你可以将最大堆改为最小堆，只需在比较时将 > 改为 < 即可，适用于需要最低优先级先处理的场景。