C / C++ / 系统课时

用优先队列调度待办任务

用优先队列调度待办任务

当待办任务不断加入时,如果每次都遍历全部任务寻找最高优先级,调度成本会随任务数增长。本节把任务优先级映射到最大堆,完成插入、查看和取出最高优先级任务的最小实现,并说明相同优先级时应怎样扩展规则。

学习目标

  • 理解最大堆为什么适合“随时取出最重要任务”的场景。
  • 用 C 语言数组实现任务入队、查看队首和出队。
  • 能根据复杂度与业务规则判断何时需要扩展或替换最大堆。

为什么最大堆适合任务调度

最大堆要求每个父节点的优先级不小于子节点,因此数组下标 0 始终保存当前最高优先级任务。查看最高优先级只需 O(1)O(1),插入和删除堆顶通过上浮、下沉恢复堆性质,成本都是 O(log⁡n)O(\log n)。

对于下标 i,父节点是 (i - 1) / 2,左子节点是 2 * i + 1,右子节点是 2 * i + 2。这让堆可以直接存放在连续数组中,不需要额外树节点指针。

最大堆与数组下标的对应关系

用数组实现最大堆

下面的程序把 priority 数值越大的任务视为越重要。push 在数组尾部插入后上浮,pop 用末尾元素替换堆顶后下沉;示例中的优先级互不相同,因此调度顺序是确定的。

c
#include <stdbool.h>
#include <stdio.h>

#define CAPACITY 16

typedef struct {
    int id;
    const char *title;
    int priority;
} Task;

typedef struct {
    Task items[CAPACITY];
    size_t size;
} PriorityQueue;

static void swap_task(Task *a, Task *b) {
    Task tmp = *a;
    *a = *b;
    *b = tmp;
}

static void sift_up(PriorityQueue *q, size_t index) {
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (q->items[parent].priority >= q->items[index].priority) {
            break;
        }
        swap_task(&q->items[parent], &q->items[index]);
        index = parent;
    }
}

static void sift_down(PriorityQueue *q, size_t index) {
    for (;;) {
        size_t left = index * 2 + 1;
        size_t right = index * 2 + 2;
        size_t largest = index;

        if (left < q->size &&
            q->items[left].priority > q->items[largest].priority) {
            largest = left;
        }
        if (right < q->size &&
            q->items[right].priority > q->items[largest].priority) {
            largest = right;
        }
        if (largest == index) {
            break;
        }

        swap_task(&q->items[index], &q->items[largest]);
        index = largest;
    }
}

static bool push(PriorityQueue *q, Task task) {
    if (q->size == CAPACITY) {
        return false;
    }

    q->items[q->size] = task;
    sift_up(q, q->size);
    q->size++;
    return true;
}

static const Task *peek(const PriorityQueue *q) {
    return q->size == 0 ? NULL : &q->items[0];
}

static bool pop(PriorityQueue *q, Task *out) {
    if (q->size == 0) {
        return false;
    }

    *out = q->items[0];
    q->size--;
    if (q->size > 0) {
        q->items[0] = q->items[q->size];
        sift_down(q, 0);
    }
    return true;
}

int main(void) {
    PriorityQueue q = {0};
    Task tasks[] = {
        {101, "修复登录故障", 90},
        {102, "整理周报", 40},
        {103, "处理付款告警", 80},
        {104, "更新文档", 30}
    };

    for (size_t i = 0; i < sizeof(tasks) / sizeof(tasks[0]); i++) {
        if (!push(&q, tasks[i])) {
            fprintf(stderr, "队列容量不足\n");
            return 1;
        }
    }

    const Task *top = peek(&q);
    printf("当前最重要: #%d %s (priority=%d)\n",
           top->id, top->title, top->priority);

    Task task;
    while (pop(&q, &task)) {
        printf("调度: #%d %s (priority=%d)\n",
               task.id, task.title, task.priority);
    }

    return 0;
}

预期输出

text
当前最重要: #101 修复登录故障 (priority=90)
调度: #101 修复登录故障 (priority=90)
调度: #103 处理付款告警 (priority=80)
调度: #102 整理周报 (priority=40)
调度: #104 更新文档 (priority=30)

数组容量、任务标题存储方式都可以按实际项目调整,但堆的关键不变量不能变:任何节点的优先级都不能高于其父节点。

调度规则与复杂度

只按一个整数优先级排序很简单,但真实任务管理器通常还需要处理“同优先级谁先执行”。常见做法是给任务增加单调递增的 sequence,比较时先看 priority,相同再让更早入队的任务胜出,这样可以得到稳定、可解释的顺序。

操作 最大堆成本 说明
查看最高优先级 O(1)O(1) 直接访问数组下标 0
新增任务 O(log⁡n)O(\log n) 尾部插入后上浮
取出最高优先级 O(log⁡n)O(\log n) 移走堆顶后下沉
查找任意任务 O(n)O(n) 纯堆不擅长按 ID 查找

什么时候需要再加一种结构

如果调度器只做“加入任务”和“取最高优先级任务”,最大堆已经足够。若还要按任务 ID 快速删除、修改优先级或查询详情,应再配合哈希索引,并让任务对象记录自己在堆中的位置。这样既保留堆的调度效率,也避免为了定位任意任务而每次线性扫描整个堆。

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

目录与阅读设置

阅读设置

17

记录一个想法

用优先队列调度待办任务

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

登录哪都通