bittern.cn
6数据结构与算法分析：C语言描述（第2版）

优先队列（堆）

堆结构

二叉堆左式堆二项堆斐波那契堆

🎯 AI 时代的学习建议：不要只读理论。理解这一章的设计动机（为什么需要这个概念？）和边界条件（什么情况下会失效？）。当 AI 生成的代码涉及这些概念时，你能判断它是否用对了场景。AI 能帮你总结内容，但无法替代你亲手阅读、思考、建立直觉的过程。

第6章：优先队列（堆）（Priority Queues / Heaps）

一、导读

1.1 本章学习目标

第6章介绍优先队列及其高效实现——堆结构。优先队列支持插入元素和提取最小（或最大）元素两种操作，在任务调度、图算法、数据压缩等领域有广泛应用。

本章的核心学习目标包括：

  • 理解优先队列的抽象定义：insert 和 deleteMin 操作的语义
  • 掌握二叉堆的实现：完全二叉树的数组表示，上浮和下沉操作
  • 学会堆排序：利用堆结构实现 O(n log n) 排序
  • 了解可并堆的概念：左式堆、二项堆如何支持高效合并
  • 理解堆在实际中的应用：Dijkstra算法、Huffman编码、Top-K问题

1.2 为什么第六章如此重要

堆是优先队列的最常用实现，它的 O(log n) 插入和删除操作使其成为需要动态维护最小/最大值场景的首选。堆排序是原地排序算法，不需要额外空间。

更重要的是，堆的思想在后续章节中反复出现：图的Dijkstra最短路径算法、最小生成树的Prim算法、事件驱动的离散事件模拟，都依赖于优先队列。

1.3 核心问题引导

为什么二叉堆用数组实现而不需要指针？父子节点的索引关系是什么？

建堆（从无序数组构建堆）的时间复杂度是多少？为什么不是 O(n log n)？

堆排序是稳定排序吗？为什么？

如何高效地找到堆中第k大的元素？

左式堆为什么能支持 O(log n) 的合并操作？

二、核心概念详解

6.1 二叉堆

二叉堆是一棵完全二叉树，满足堆序性：每个节点的值都不大于（最小堆）或不小于（最大堆）其子节点的值。

c
#define MAX_ELEMENTS 1000

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

PriorityQueue *createPQ(int cap) {
    PriorityQueue *PQ = (PriorityQueue *)malloc(sizeof(PriorityQueue));
    PQ->capacity = cap;
    PQ->size = 0;
    PQ->array = (int *)malloc(cap * sizeof(int));
    return PQ;
}

int parent(int i) { return (i - 1) / 2; }
int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }

void swap(int *a, int *b) {
    int tmp = *a; *a = *b; *b = tmp;
}

// 上浮操作：插入时从底部向上调整
void percolateUp(PriorityQueue *PQ, int i) {
    while (i > 0 && PQ->array[parent(i)] > PQ->array[i]) {
        swap(&PQ->array[i], &PQ->array[parent(i)]);
        i = parent(i);
    }
}

// 插入 - O(log n)
void insert(PriorityQueue *PQ, int val) {
    if (PQ->size >= PQ->capacity) return;
    PQ->array[PQ->size] = val;
    percolateUp(PQ, PQ->size);
    PQ->size++;
}

// 下沉操作：删除最小值后从顶部向下调整
void percolateDown(PriorityQueue *PQ, int i) {
    while (1) {
        int smallest = i;
        if (left(i) < PQ->size && PQ->array[left(i)] < PQ->array[smallest])
            smallest = left(i);
        if (right(i) < PQ->size && PQ->array[right(i)] < PQ->array[smallest])
            smallest = right(i);
        if (smallest == i) break;
        swap(&PQ->array[i], &PQ->array[smallest]);
        i = smallest;
    }
}

// 删除最小值 - O(log n)
int deleteMin(PriorityQueue *PQ) {
    if (PQ->size == 0) return -1;
    int minVal = PQ->array[0];
    PQ->array[0] = PQ->array[--PQ->size];
    percolateDown(PQ, 0);
    return minVal;
}

// 建堆 - O(n)
void buildHeap(PriorityQueue *PQ, int arr[], int n) {
    PQ->size = n;
    for (int i = 0; i < n; i++)
        PQ->array[i] = arr[i];
    // 从最后一个非叶节点开始，逐个下沉
    for (int i = n / 2 - 1; i >= 0; i--)
        percolateDown(PQ, i);
}
// 建堆O(n)的直觉：大部分节点在底层，只需少量调整

6.2 堆排序

c
// 堆排序 - O(n log n)
void heapSort(int arr[], int n) {
    // 建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        // percolateDown for max heap
        int curr = i;
        while (1) {
            int largest = curr;
            if (2*curr+1 < n && arr[2*curr+1] > arr[largest]) largest = 2*curr+1;
            if (2*curr+2 < n && arr[2*curr+2] > arr[largest]) largest = 2*curr+2;
            if (largest == curr) break;
            swap(&arr[curr], &arr[largest]);
            curr = largest;
        }
    }
    // 逐个提取最大值放到末尾
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        int curr = 0, size = i;
        while (1) {
            int largest = curr;
            if (2*curr+1 < size && arr[2*curr+1] > arr[largest]) largest = 2*curr+1;
            if (2*curr+2 < size && arr[2*curr+2] > arr[largest]) largest = 2*curr+2;
            if (largest == curr) break;
            swap(&arr[curr], &arr[largest]);
            curr = largest;
        }
    }
}
// 堆排序是不稳定的（交换可能改变相等元素的相对顺序）
// 空间复杂度O(1)（原地排序）

6.3 左式堆

左式堆是一种支持高效合并的可并堆。它通过维护"零路径长"（null path length, npl）来保证树的平衡性。

c
typedef struct LeftistNode {
    int element;
    struct LeftistNode *left;
    struct LeftistNode *right;
    int npl;  // null path length
} LeftistNode;

// 合并两个左式堆 - O(log n)
LeftistNode *merge(LeftistNode *h1, LeftistNode *h2) {
    if (h1 == NULL) return h2;
    if (h2 == NULL) return h1;
    if (h1->element > h2->element) {
        LeftistNode *tmp = h1; h1 = h2; h2 = tmp;
    }
    h1->right = merge(h1->right, h2);
    if (h1->left == NULL || 
        h1->left->npl < h1->right->npl) {
        LeftistNode *tmp = h1->left;
        h1->left = h1->right;
        h1->right = tmp;
    }
    h1->npl = (h1->right == NULL) ? 0 : h1->right->npl + 1;
    return h1;
}

三、实战案例

3.1 Top-K问题

c
// 从n个元素中找出最大的k个元素
// 方法：维护一个大小为k的最小堆
void topK(int arr[], int n, int k) {
    PriorityQueue *PQ = createPQ(k);
    // 先用前k个元素建堆
    for (int i = 0; i < k; i++)
        insert(PQ, arr[i]);
    // 遍历剩余元素
    for (int i = k; i < n; i++) {
        if (arr[i] > PQ->array[0]) {
            deleteMin(PQ);
            insert(PQ, arr[i]);
        }
    }
    // 堆中的k个元素就是最大的k个
    printf("Top %d elements:\n", k);
    while (PQ->size > 0)
        printf("%d ", deleteMin(PQ));
    printf("\n");
}
// 时间复杂度：O(n log k)，远优于排序的O(n log n)

四、本章小结

优先队列支持 insert 和 deleteMin 操作。

二叉堆是完全二叉树的数组实现，插入和删除均为 O(log n)。

建堆的时间复杂度为 O(n)，而非 O(n log n)。

堆排序是原地、不稳定的 O(n log n) 排序算法。

左式堆支持 O(log n) 的合并操作。

五、思考与练习

思考题

为什么建堆是 O(n) 而不是 O(n log n)？

如何用堆实现一个高效的定时器（管理多个定时事件）？

二项堆的合并为什么是 O(log n)？

编程练习

实现一个支持 decreaseKey 操作的二叉堆。

用优先队列实现 Dijkstra 最短路径算法。

实现堆排序并与快速排序对比性能。

6/10优先队列
0%