第14章堆与优先队列

课程目录第14章堆与优先队列

第14章堆与优先队列：从底层原理到工程实践

堆（Heap）这个东西，说实话我刚开始学的时候觉得挺绕的。明明叫“堆”，却跟内存里的堆区没啥关系。它其实是一种特殊的完全二叉树，专门用来解决一类问题——快速找到一堆数里的最大值或最小值。

我在项目中遇到过好几次这样的场景：系统里有一堆任务，每个任务有优先级，我需要每次都取出优先级最高的那个去执行。如果用普通数组，每次找最大值都要遍历一遍，数据量大了根本扛不住。这时候，堆就派上用场了。

堆的定义与性质

堆本质上是一棵完全二叉树，但它多了两条硬性规定：

结构性质：它必须是一棵完全二叉树。也就是说，除了最后一层，其他层都是满的，最后一层的节点都靠左排列。
堆序性质：任意节点的值，都大于等于（或小于等于）它的子节点。

根据堆序性质，堆分为两种：

大顶堆（最大堆）：父节点 ≥ 子节点。根节点是最大值。
小顶堆（最小堆）：父节点 ≤ 子节点。根节点是最小值。

核心要点：堆只保证父子节点之间的大小关系，不保证兄弟节点之间的大小关系。这一点跟二叉搜索树完全不同，别搞混了。

你想想看，如果我要找最大值，大顶堆直接把根节点拿出来就行了，时间复杂度 O(1)。这就是堆最迷人的地方。

堆的存储结构

堆虽然逻辑上是二叉树，但实际存储用的是数组。为什么？因为完全二叉树天然适合用数组存，没有空间浪费。

我用一个数组来存堆，下标从 0 开始。对于下标为 i 的节点：

父节点下标：(i - 1) / 2
左子节点下标：2 * i + 1
右子节点下标：2 * i + 2

举个例子，数组 [50, 30, 40, 10, 20, 35] 对应的大顶堆长这样：

个人习惯：我一般用下标 0 作为第一个元素。有些教材从 1 开始，父节点是 i/2，这样位运算更快。但我觉得从 0 开始更符合 C 语言的习惯，代码也更直观。

堆的插入与删除：上浮与下沉

堆的两个核心操作就是插入和删除。这两个操作分别依赖两个关键过程——上浮（Shift Up）和下沉（Shift Down）。

插入操作（上浮）

插入一个新元素时，我先把元素放到数组末尾（也就是完全二叉树的最后一个位置）。然后让它跟父节点比较，如果比父节点大（大顶堆），就交换位置，一直往上走，直到满足堆序性质。

这个过程就叫「上浮」。代码实现很简单：

void shiftUp(int heap[], int i) {
    while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void insert(int heap[], int *size, int val) {
    heap[*size] = val;
    (*size)++;
    shiftUp(heap, *size - 1);
}

时间复杂度 O(log n)，因为树的高度就是 log n。

删除操作（下沉）

删除操作通常指的是删除根节点（最大值或最小值）。做法是：把根节点跟最后一个元素交换，然后删除最后一个元素（size--）。接着从根节点开始，跟它较大的子节点比较，如果比子节点小，就交换，一直往下走。

这个过程叫「下沉」。

void shiftDown(int heap[], int size, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left] > heap[largest])
        largest = left;
    if (right < size && heap[right] > heap[largest])
        largest = right;

    if (largest != i) {
        swap(&heap[i], &heap[largest]);
        shiftDown(heap, size, largest);
    }
}

int deleteRoot(int heap[], int *size) {
    int root = heap[0];
    heap[0] = heap[*size - 1];
    (*size)--;
    shiftDown(heap, *size, 0);
    return root;
}

我曾经踩过的坑：下沉操作里，一定要先判断子节点下标是否越界。我刚开始写的时候忘了检查 left < size，结果数组越界，查了半天 bug。记住，完全二叉树虽然紧凑，但最后一层可能不满。

堆排序

堆排序的思路其实很直接：先把数组构建成一个大顶堆，然后反复把根节点（最大值）取出来，放到数组末尾，再调整堆。

具体步骤：

建堆：从最后一个非叶子节点开始，依次执行下沉操作。
排序：交换根节点和最后一个元素，堆大小减 1，然后对根节点下沉。
重复步骤 2，直到堆为空。

建堆的代码：

void buildHeap(int heap[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        shiftDown(heap, size, i);
    }
}

为什么从 size/2 - 1 开始？因为最后一个非叶子节点的下标就是 size/2 - 1。叶子节点不需要下沉，它们已经满足堆序性质了。

完整的堆排序：

void heapSort(int arr[], int n) {
    buildHeap(arr, n);
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        shiftDown(arr, i, 0);
    }
}

堆排序的时间复杂度是 O(n log n)，空间复杂度 O(1)。它是不稳定的排序算法——因为下沉操作可能改变相同元素的相对顺序。

性能对比：堆排序在实际工程中不如快速排序常用，因为它的缓存局部性较差（数组访问跳跃较大）。但在需要稳定 O(n log n) 最坏时间复杂度的场景下，堆排序是可靠的选择。

优先队列的实现

优先队列说白了就是一个队列，但出队的时候不是先进先出，而是优先级最高的先出。堆是实现优先队列最经典的数据结构。

用堆实现优先队列，核心接口就几个：

操作	描述	时间复杂度
push	插入一个元素	O(log n)
pop	删除优先级最高的元素	O(log n)
top	获取优先级最高的元素	O(1)
empty	判断队列是否为空	O(1)

一个简单的优先队列实现：

typedef struct {
    int *data;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createQueue(int cap) {
    PriorityQueue *q = malloc(sizeof(PriorityQueue));
    q->data = malloc(cap * sizeof(int));
    q->size = 0;
    q->capacity = cap;
    return q;
}

void push(PriorityQueue *q, int val) {
    if (q->size >= q->capacity) {
        // 扩容处理，这里省略
        return;
    }
    q->data[q->size] = val;
    q->size++;
    shiftUp(q->data, q->size - 1);
}

int pop(PriorityQueue *q) {
    if (q->size == 0) return -1;
    return deleteRoot(q->data, &q->size);
}

int top(PriorityQueue *q) {
    if (q->size == 0) return -1;
    return q->data[0];
}

工程建议：在实际项目中，我一般不会手写优先队列，直接用现成的库。但理解底层原理很重要——有一次我在嵌入式系统里需要自己实现，因为标准库不支持。那时候就庆幸自己当初把堆搞明白了。

堆的核心操作流程图

下面这张图总结了堆的整个操作流程，从插入到删除，再到堆排序：

堆这个数据结构，说难不难，说简单也不简单。它的核心就两个动作——上浮和下沉。搞懂了这两个，堆排序和优先队列就水到渠成了。

我个人觉得，堆是那种「看起来简单，但写起来容易出 bug」的数据结构。边界条件、下标计算、递归深度……稍不注意就翻车。但只要你亲手实现过两三遍，这些细节就会变成肌肉记忆。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录