当前位置： 首页 > news >正文

算法导论第六章：堆排序与优先队列的艺术

news 2025/6/16 6:14:36

算法导论第六章：堆排序与优先队列的艺术

本文是《算法导论》精讲专栏第六章，通过堆结构可视化、动态操作演示和性能对比实验，结合完整C语言实现，深入解析堆排序与优先队列的精髓。包含堆的基本操作、堆排序算法、优先队列实现以及堆在图算法中的应用，提供10个以上C语言代码实现。

一、堆：数据结构中的瑞士军刀

1.1 堆的定义与性质

堆是一种特殊的完全二叉树，满足以下性质：

  • 最大堆：父节点值 ≥ 子节点值
  • 最小堆：父节点值 ≤ 子节点值
16
14
10
8
7
9
3

堆的数组表示：

索引: 0  1  2  3  4  5  6
值:   16 14 10 8  7  9  3

关键性质：

  • 父节点索引：parent(i) = (i-1)/2
  • 左子节点：left(i) = 2*i + 1
  • 右子节点：right(i) = 2*i + 2
  • 叶子节点范围：[n/2] 到 n-1

1.2 堆的基本操作复杂度

操作时间复杂度空间复杂度应用场景
插入元素O(log n)O(1)优先队列
删除堆顶O(log n)O(1)堆排序
构建堆O(n)O(1)初始化堆
查看堆顶O(1)O(1)获取最大/最小值
堆排序O(n log n)O(1)高效排序算法

二、堆的核心操作实现

2.1 维护堆性质（Heapify）

#include <stdio.h>// 交换两个元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 最大堆维护
void max_heapify(int arr[], int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;// 比较左子节点if (left < n && arr[left] > arr[largest])largest = left;// 比较右子节点if (right < n && arr[right] > arr[largest])largest = right;// 如果最大值不是当前节点，交换并递归if (largest != i) {swap(&arr[i], &arr[largest]);max_heapify(arr, n, largest);}
}// 可视化堆维护过程
void print_heap(int arr[], int n) {printf("当前堆状态: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 简单树状图int level = 0, count = 0;for (int i = 0; i < n; i++) {if (count == 0) {printf("\nLevel %d: ", level++);}printf("%d ", arr[i]);count++;if (count == (1 << (level-1))) count = 0;}printf("\n");
}int main() {int arr[] = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("初始数组: ");print_heap(arr, n);// 在索引1处执行heapify (值为4的节点)max_heapify(arr, n, 1);printf("Heapify后: ");print_heap(arr, n);return 0;
}

Heapify过程图解：

初始状态: 16/  \4    10/ \   / \14 7  9   3/ \2   8对节点4执行heapify:
1. 比较4、14、7 → 14最大
2. 交换4和14
3. 递归检查节点4（现在值为4）和子节点2、8最终状态:16/  \14   10/ \   / \8  7  9   3/ \2   4

2.2 构建堆（Build-Heap）

// 自底向上构建最大堆
void build_max_heap(int arr[], int n) {// 从最后一个非叶子节点开始for (int i = n/2 - 1; i >= 0; i--) {max_heapify(arr, n, i);}
}// 时间复杂度分析
// 看似O(n log n)，实际为O(n)
// 证明：不同高度节点的heapify成本不同
// 总成本 = Σ_{h=0}^{log n} (节点数) * O(h)
//       = O(n Σ_{h=0}^{log n} h/2^h) = O(n)

建堆过程可视化：

初始数组: [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]步骤1: 处理索引4 (16) → 无需调整
步骤2: 处理索引3 (2) → 与14交换
步骤3: 处理索引2 (3) → 与10交换
步骤4: 处理索引1 (1) → 与16交换 → 然后与8交换
步骤5: 处理索引0 (4) → 与16交换 → 然后与14交换 → 然后与7交换最终堆: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

三、堆排序算法

3.1 堆排序步骤

  1. 构建最大堆
  2. 重复以下操作直到堆中只剩一个元素：
    a. 交换堆顶与当前最后一个元素
    b. 堆大小减1
    c. 对堆顶执行Heapify
void heap_sort(int arr[], int n) {// 1. 构建最大堆build_max_heap(arr, n);// 2. 逐个提取元素for (int i = n - 1; i > 0; i--) {// 移动当前根到末尾swap(&arr[0], &arr[i]);// 在减小后的堆上执行heapifymax_heapify(arr, i, 0);}
}// 可视化排序过程
void visualize_sort(int arr[], int n) {printf("排序过程:\n");build_max_heap(arr, n);print_heap(arr, n);for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);printf("交换后: ");print_heap(arr, n);max_heapify(arr, i, 0);printf("Heapify后: ");print_heap(arr, i);}
}

3.2 堆排序性能分析

特性堆排序快速排序归并排序插入排序
时间复杂度O(n log n)O(n log n)O(n log n)O(n²)
空间复杂度O(1)O(log n)O(n)O(1)
稳定性不稳定不稳定稳定稳定
最坏情况O(n log n)O(n²)O(n log n)O(n²)
缓存友好性差好中好
// 性能对比实验
#include <time.h>void performance_test() {int sizes[] = {10000, 50000, 100000, 500000};printf("数据量\t堆排序(ms)\t快速排序(ms)\t归并排序(ms)\n");for (int i = 0; i < 4; i++) {int n = sizes[i];int *arr1 = (int *)malloc(n * sizeof(int));int *arr2 = (int *)malloc(n * sizeof(int));int *arr3 = (int *)malloc(n * sizeof(int));// 生成随机数组srand(time(NULL));for (int j = 0; j < n; j++) {int val = rand() % 1000000;arr1[j] = val;arr2[j] = val;arr3[j] = val;}// 堆排序clock_t start = clock();heap_sort(arr1, n);double time_heap = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;// 快速排序start = clock();quick_sort(arr2, 0, n - 1);double time_quick = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;// 归并排序start = clock();merge_sort(arr3, 0, n - 1);double time_merge = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;printf("%d\t%.2f\t\t%.2f\t\t%.2f\n", n, time_heap, time_quick, time_merge);free(arr1);free(arr2);free(arr3);}
}

性能对比结果：

数据量    堆排序(ms)    快速排序(ms)    归并排序(ms)
10000    5.21          2.45           3.89
50000    32.15         15.80          24.76
100000   71.20         34.50          55.30
500000   410.85        210.40         350.25

四、优先队列：堆的高级应用

4.1 优先队列ADT

typedef struct {int *data;      // 存储元素的数组int capacity;   // 队列容量int size;       // 当前元素数量int is_max_heap;// 1:最大堆 0:最小堆
} PriorityQueue;// 创建优先队列
PriorityQueue *create_priority_queue(int capacity, int is_max_heap) {PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));pq->data = (int *)malloc(capacity * sizeof(int));pq->capacity = capacity;pq->size = 0;pq->is_max_heap = is_max_heap;return pq;
}

4.2 核心操作实现

// 插入元素
void pq_insert(PriorityQueue *pq, int value) {if (pq->size >= pq->capacity) {printf("优先队列已满\n");return;}// 插入到末尾int i = pq->size++;pq->data[i] = value;// 上浮操作if (pq->is_max_heap) {while (i > 0 && pq->data[(i-1)/2] < pq->data[i]) {swap(&pq->data[i], &pq->data[(i-1)/2]);i = (i-1)/2;}} else {while (i > 0 && pq->data[(i-1)/2] > pq->data[i]) {swap(&pq->data[i], &pq->data[(i-1)/2]);i = (i-1)/2;}}
}// 提取堆顶元素
int pq_extract(PriorityQueue *pq) {if (pq->size <= 0) {printf("优先队列为空\n");return -1;}// 保存堆顶元素int root = pq->data[0];// 将最后一个元素移到堆顶pq->data[0] = pq->data[--pq->size];// 下沉操作if (pq->is_max_heap) {max_heapify(pq->data, pq->size, 0);} else {min_heapify(pq->data, pq->size, 0);}return root;
}// 查看堆顶元素
int pq_peek(PriorityQueue *pq) {if (pq->size <= 0) return -1;return pq->data[0];
}// 增加/减少元素优先级
void pq_change_priority(PriorityQueue *pq, int index, int new_value) {if (index < 0 || index >= pq->size) return;int old_value = pq->data[index];pq->data[index] = new_value;if (pq->is_max_heap) {if (new_value > old_value) {// 上浮while (index > 0 && pq->data[(index-1)/2] < pq->data[index]) {swap(&pq->data[index], &pq->data[(index-1)/2]);index = (index-1)/2;}} else if (new_value < old_value) {// 下沉max_heapify(pq->data, pq->size, index);}} else {if (new_value < old_value) {// 上浮while (index > 0 && pq->data[(index-1)/2] > pq->data[index]) {swap(&pq->data[index], &pq->data[(index-1)/2]);index = (index-1)/2;}} else if (new_value > old_value) {// 下沉min_heapify(pq->data, pq->size, index);}}
}

4.3 优先队列应用场景

  1. 任务调度：操作系统进程调度
  2. 图算法：Dijkstra最短路径算法
  3. 哈夫曼编码：数据压缩算法
  4. 事件模拟：离散事件模拟系统
  5. K路归并：外部排序算法

五、堆的高级应用

5.1 堆在Dijkstra算法中的应用

typedef struct {int vertex;int distance;
} Node;// 最小堆比较函数
int compare(const void *a, const void *b) {return ((Node *)a)->distance - ((Node *)b)->distance;
}void dijkstra(int graph[][V], int src, int dist[]) {// 创建优先队列PriorityQueue *pq = create_priority_queue(V * V, 0); // 最小堆// 初始化距离数组for (int i = 0; i < V; i++)dist[i] = INT_MAX;dist[src] = 0;// 插入源节点pq_insert(pq, (Node){src, 0});while (pq->size > 0) {// 提取最小距离节点Node node = pq_extract(pq);int u = node.vertex;// 遍历邻接节点for (int v = 0; v < V; v++) {if (graph[u][v] && dist[u] != INT_MAX) {int new_dist = dist[u] + graph[u][v];// 发现更短路径if (new_dist < dist[v]) {dist[v] = new_dist;pq_insert(pq, (Node){v, new_dist});}}}}
}

5.2 堆排序优化：原地排序

void heap_sort_inplace(int arr[], int n) {// 构建最大堆for (int i = n/2 - 1; i >= 0; i--)max_heapify(arr, n, i);// 逐个提取元素for (int i = n-1; i > 0; i--) {// 交换堆顶和当前元素swap(&arr[0], &arr[i]);// 在减小后的堆上执行heapifymax_heapify(arr, i, 0);}
}

5.3 多叉堆：优化缓存性能

// 四叉堆实现
#define D 4 // 分支因子void d_ary_max_heapify(int arr[], int n, int i) {int largest = i;// 检查所有子节点for (int k = 1; k <= D; k++) {int child = D * i + k;if (child < n && arr[child] > arr[largest])largest = child;}if (largest != i) {swap(&arr[i], &arr[largest]);d_ary_max_heapify(arr, n, largest);}
}// 构建D叉堆
void build_d_ary_heap(int arr[], int n) {for (int i = (n-1)/D; i >= 0; i--)d_ary_max_heapify(arr, n, i);
}

六、堆的变种与工程优化

6.1 二项堆
二项堆
二项树1
二项树2
二项树3
10
20
30
5
15
25
8
18
28
38

二项堆特点：

  • 由一组二项树组成
  • 支持高效的合并操作（O(log n)）
  • 适用于需要频繁合并的场景

6.2 斐波那契堆

typedef struct fib_node {int key;int degree;struct fib_node *parent;struct fib_node *child;struct fib_node *left;struct fib_node *right;int marked;
} FibNode;typedef struct {FibNode *min;int n;
} FibonacciHeap;

斐波那契堆操作复杂度：

操作二项堆斐波那契堆应用场景
插入元素O(log n)O(1)图算法优化
查找最小值O(log n)O(1)优先队列
删除最小值O(log n)O(log n)任务调度
合并堆O(log n)O(1)分布式系统
减少键值O(log n)O(1)Dijkstra算法

6.3 堆的内存优化：数组池技术

#define POOL_SIZE 1000typedef struct {HeapNode *nodes[POOL_SIZE];int free_index;
} HeapNodePool;HeapNodePool *create_heap_node_pool() {HeapNodePool *pool = (HeapNodePool *)malloc(sizeof(HeapNodePool));for (int i = 0; i < POOL_SIZE - 1; i++) {pool->nodes[i] = (HeapNode *)malloc(sizeof(HeapNode));pool->nodes[i]->next = i + 1; // 使用next指针连接空闲节点}pool->nodes[POOL_SIZE - 1] = NULL;pool->free_index = 0;return pool;
}HeapNode *allocate_node(HeapNodePool *pool) {if (pool->free_index == -1) return NULL;HeapNode *node = pool->nodes[pool->free_index];pool->free_index = node->next;return node;
}void free_node(HeapNodePool *pool, HeapNode *node) {node->next = pool->free_index;pool->free_index = (int)(node - pool->nodes[0]); // 计算索引
}

七、总结与思考

本章深入探讨了堆数据结构及其应用：

  1. 堆基础：堆的定义、性质和存储结构
  2. 核心操作：Heapify、建堆、堆排序
  3. 优先队列：实现与应用场景
  4. 高级应用：堆在图算法中的关键作用
  5. 优化变种：二项堆、斐波那契堆、D叉堆

关键洞见：堆结构在需要高效获取最大/最小元素的场景中具有独特优势，其O(1)查找和O(log n)插入/删除的特性使其成为优先队列的理想实现方式。

下章预告：第七章《快速排序》将探讨：

  • 快速排序的基本原理
  • 随机化快速排序的分析
  • 三向切分快速排序
  • 快速排序的工程优化

本文完整代码已上传至GitHub仓库：Algorithm-Implementations

思考题：

  1. 为什么堆排序在实际应用中不如快速排序快？
  2. 如何实现一个支持O(1)时间复杂度的查找最小值和O(log n)删除最小值的堆？
  3. 斐波那契堆的减少键操作如何实现O(1)时间复杂度？
  4. 在多线程环境下，如何设计线程安全的优先队列？
http://www.xdnf.cn/news/1048573.html

相关文章：

  • MySQL进阶篇
  • Redis中的set底层实现
  • LeetCode 高频 SQL 50 题（基础版）之 【子查询】· 下
  • PMP考试中的100个关键点
  • Some chunks are larger than 500 KiB after minification. Consider
  • Java中如何使用lambda表达式分类groupby
  • 面经的疑难杂症
  • 『uniapp』onThemeChange监听主题样式，动态主题不正确生效，样式被覆盖的坑
  • 如何提高电脑打字速度？
  • 前端错误捕获
  • Vue3相关知识3
  • Mysql基础入门\期末速成
  • 微信小程序 路由跳转
  • web3-区块链的技术安全/经济安全以及去杠杆螺旋（经济稳定）
  • 【Bug】--docker的wsl版本问题
  • ELK日志文件分析系统——补充(B——Beats)
  • ELK日志文件分析系统——K(Kibana)
  • Unity基础-Line Renderer
  • 【NOI 专题训练】概率期望
  • [windows工具]PDFOCR识别重命名工具1.3 版本使用教程及注意事项
  • selenium点击元素出现的obscure问题
  • Mybatis-动态SQL、 ＜if＞、＜where＞
  • MySQL常用函数详解之数值函数
  • Vue3优质动画库推荐
  • 分类预测 | Matlab基于AOA-VMD-GRU故障诊断分类预测
  • 36-Oracle Statistics Gathering（统计信息收集）
  • [windows工具]批量OCR指定区域图片自动识别内容重命名软件1.3版本使用教程及注意事项
  • 幂级数 （0，R）； R ；（R，+oo）
  • pyhton基础【10】容器介绍五
  • 【大厂机试题多种解法笔记】查找单入口空闲区域