C / C++ / 系统课时
用最大堆实现优先队列
用最大堆实现优先队列
优先队列关心的不是“谁先进入”,而是“谁的优先级最高”。本节把最大堆封装成一个小型 C 接口,完成入队、查看最高优先级和出队,并用可运行程序验证删除堆顶后的下沉过程。
学习目标
- 说明最大堆为什么能支持快速获取最高优先级元素。
- 用 C 封装
push、peek、pop三个基础操作。 - 理解上浮、下沉过程中必须保持的堆不变量和复杂度。
最大堆如何对应优先队列
最大堆要求任意父节点的值都不小于子节点,因此数组下标 0 始终保存当前最大值。把“数值越大,优先级越高”作为约定后,查看最高优先级只需读取堆顶;插入时从末尾上浮,删除堆顶时用末尾元素补位后再下沉。

数组实现堆时,节点下标关系固定:父节点是 (i - 1) / 2,左孩子是 2 * i + 1,右孩子是 2 * i + 2。因此不需要额外的指针结构,也能在连续内存中完成调整。
用结构体封装堆操作
下面实现一个容量固定的基础优先队列。示例只存整数优先级,便于把注意力放在堆操作本身;实际项目可以把数组元素替换成任务结构体,并在比较时读取其中的优先级字段。
c
#include <stdbool.h>
#include <stdio.h>
#define PQ_CAPACITY 16
typedef struct {
int heap[PQ_CAPACITY];
int size;
} PriorityQueue;
static void swap_int(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
static bool pq_push(PriorityQueue *pq, int value) {
if (pq->size >= PQ_CAPACITY) {
return false;
}
int i = pq->size++;
pq->heap[i] = value;
/* 新元素从末尾向上移动,直到父节点已经不小于它。 */
while (i > 0) {
int parent = (i - 1) / 2;
if (pq->heap[parent] >= pq->heap[i]) {
break;
}
swap_int(&pq->heap[parent], &pq->heap[i]);
i = parent;
}
return true;
}
static bool pq_peek(const PriorityQueue *pq, int *out) {
if (pq->size == 0) {
return false;
}
*out = pq->heap[0];
return true;
}
static bool pq_pop(PriorityQueue *pq, int *out) {
if (pq->size == 0) {
return false;
}
*out = pq->heap[0];
pq->size--;
if (pq->size == 0) {
return true;
}
pq->heap[0] = pq->heap[pq->size];
int i = 0;
/* 每次与两个孩子中更大的那个比较,避免破坏最大堆性质。 */
while (1) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < pq->size && pq->heap[left] > pq->heap[largest]) {
largest = left;
}
if (right < pq->size && pq->heap[right] > pq->heap[largest]) {
largest = right;
}
if (largest == i) {
break;
}
swap_int(&pq->heap[i], &pq->heap[largest]);
i = largest;
}
return true;
}
int main(void) {
PriorityQueue pq = {0};
int values[] = {30, 10, 50, 40};
for (int i = 0; i < 4; ++i) {
if (!pq_push(&pq, values[i])) {
fprintf(stderr, "queue is full\n");
return 1;
}
}
int value;
if (pq_peek(&pq, &value)) {
printf("highest=%d\n", value);
}
printf("order:");
while (pq_pop(&pq, &value)) {
printf(" %d", value);
}
printf("\n");
return 0;
}预期结果:程序先读到堆顶 50,随后连续出队时得到从高到低的优先级顺序。相同优先级元素在这个基础实现中不保证稳定顺序。
运行与验证
将代码保存为 priority_queue.c,使用支持 C11 的编译器构建并运行:
bash
cc -std=c11 -Wall -Wextra -O2 priority_queue.c -o priority_queue && ./priority_queue预期输出:
text
highest=50
order: 50 40 30 10如果实际编译器可执行文件不是 cc,可替换为本机的 gcc 或 clang;输出内容不受该替换影响。
复杂度与边界
pq_peek 直接读取堆顶,时间复杂度为 O(1);pq_push 最坏需要沿树高上浮,pq_pop 最坏需要沿树高下沉,两者都是 O(log n)。固定数组让实现简单,但容量满时必须返回失败,不能继续写入数组。
空队列时,peek 和 pop 都通过 false 明确表示“没有元素”,调用方不能直接读取未赋值结果。若业务还要求“相同优先级按进入顺序处理”,需要额外保存序号,并把“优先级 + 序号”共同纳入比较规则。
按自己的节奏,确认真正理解。