C 语言数据结构与算法：堆与优先级队列——TopK问题的最优解
做嵌入式开发的同学，肯定都踩过“动态找最值”的坑：调试时日志刷了一屏幕，关键的错误日志却被一堆调试信息淹没，翻半天找不到；传感器实时采集数据，要快速筛选出波动最大的几个值，用数组遍历查找不仅慢，还占用宝贵的MCU资源；RTOS任务调度时，高优先级任务急着执行，低优先级任务却在抢资源……这些场景里，普通数组、链表根本扛不住，效率低还费内存。
而今天要讲的堆（Heap）与优先级队列，就是解决这类问题的“神器”——它基于完全二叉树，找最值、插入删除元素都只要O(logn)的时间，用数组存储还不用额外的指针开销，完美适配嵌入式系统内存受限、实时性要求高的特点。接下来，咱们从原理讲到实战，用最接地气的语言+符合MISRA C规范的代码，把堆和优先级队列彻底讲明白，不管是面试还是项目实战都能直接用。
一、堆的核心原理
堆是一种完全二叉树（除最后一层外，每一层都被填满；最后一层节点靠左排列），核心特性是“父节点与子节点的数值关系”，分为两种类型：
大顶堆：任意父节点的值 ≥ 其左右子节点的值（堆顶为最大值）；
小顶堆：任意父节点的值 ≤ 其左右子节点的值（堆顶为最小值）。
1.1 堆的数组存储方式
嵌入式系统中，二叉树的链式存储会带来额外的指针开销（尤其MCU内存受限场景），因此堆通常用数组存储，利用完全二叉树的特性通过索引计算父子节点位置：
假设堆的数组为
heap[]
父节点索引：
parent = (i - 1) / 2
左子节点索引：
left = 2 * i + 1
右子节点索引：
right = 2 * i + 2
示例（小顶堆）：
1
/
3 2
/ /
6 5 4
数组存储为：
[1, 3, 2, 6, 5, 4]
二、堆的关键实现
以下实现基于小顶堆（大顶堆仅需修改比较逻辑），代码遵循MISRA C规范（禁用裸指针、边界检查、避免魔法数），适配嵌入式内存受限场景（静态数组+容量限制）。
2.1 堆的结构体定义
/* 堆的最大容量（根据嵌入式场景调整，如日志系统可设64/128） */
#define HEAP_MAX_CAPACITY 128
/* 小顶堆结构体 */
typedef struct {
int data[HEAP_MAX_CAPACITY]; /* 堆数据存储 */
uint32_t size; /* 当前堆元素个数 */
} MinHeap;
2.2 核心操作：堆化（Heapify）
堆化是维护堆特性的核心操作，分为“自上而下堆化”（删除根节点后）和“自下而上堆化”（插入新节点后）。
2.2.1 自上而下堆化（修复堆）
/**
* @brief 小顶堆自上而下堆化（修复堆）
* @param heap 堆结构体指针
* @param idx 待堆化的节点索引
*/
static void heapify_down(MinHeap *heap, uint32_t idx) {
if (heap == NULL || idx >= heap->size) {
return;
}
uint32_t min_idx = idx;
while (1) {
/* 找左子节点 */
const uint32_t left = 2 * idx + 1;
/* 找右子节点 */
const uint32_t right = 2 * idx + 2;
/* 比较左子节点 */
if (left < heap->size && heap->data[left] < heap->data[min_idx]) {
min_idx = left;
}
/* 比较右子节点 */
if (right < heap->size && heap->data[right] < heap->data[min_idx]) {
min_idx = right;
}
/* 已是最小节点，退出 */
if (min_idx == idx) {
break;
}
/* 交换当前节点与最小子节点 */
const int temp = heap->data[idx];
heap->data[idx] = heap->data[min_idx];
heap->data[min_idx] = temp;
/* 继续向下堆化 */
idx = min_idx;
}
}
2.2.2 自下而上堆化（插入修复）
/**
* @brief 小顶堆自下而上堆化（插入后修复）
* @param heap 堆结构体指针
* @param idx 待堆化的节点索引
*/
static void heapify_up(MinHeap *heap, uint32_t idx) {
if (heap == NULL || idx == 0 ||© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...