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 明确表示“没有元素”,调用方不能直接读取未赋值结果。若业务还要求“相同优先级按进入顺序处理”,需要额外保存序号,并把“优先级 + 序号”共同纳入比较规则。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用最大堆实现优先队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通