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

【附C源码】从零实现C语言堆数据结构：原理、实现与应用

news 2026/5/16 15:37:10

【附C源码】从零实现C语言堆数据结构：原理、实现与应用

堆（Heap）作为优先级队列的经典实现，在任务调度、图算法（如Dijkstra、Prim）、Top-K问题等场景中有着广泛应用。本文将深入探讨堆的核心原理，并基于C语言标准库实现一个完整的、可用于生产环境的最小堆与最大堆。

一、堆的本质与性质

堆是一种特殊的完全二叉树，其核心特性在于父节点与子节点之间的序关系：

最小堆：任意节点的值不大于其子节点的值，堆顶为全局最小值
最大堆：任意节点的值不小于其子节点的值，堆顶为全局最大值

由于完全二叉树的结构特性，堆可以高效地映射到数组中存储，避免了指针带来的额外内存开销。

数组映射关系

对于索引为iii的节点：

父节点索引：parent(i)=⌊(i−1)/2⌋parent(i) = \lfloor (i-1)/2 \rfloorparent(i)=⌊(i−1)/2⌋
左子节点索引：left(i)=2i+1left(i) = 2i + 1left(i)=2i+1
右子节点索引：right(i)=2i+2right(i) = 2i + 2right(i)=2i+2

二、核心操作的时间复杂度分析

操作	时间复杂度	说明
插入元素	O(log⁡n)O(\log n)O(logn)	从叶节点向上调整
删除堆顶	O(log⁡n)O(\log n)O(logn)	将尾元素移至堆顶后向下调整
查看堆顶	O(1)O(1)O(1)	直接访问数组首元素
Floyd建堆	O(n)O(n)O(n)	自底向上批量建堆，优于逐元素插入

Floyd建堆的线性复杂度是一个常被忽视但极为重要的优化点。对于nnn个元素的建堆过程，时间复杂度可推导为：

T(n)=∑h=0⌊log⁡n⌋⌈n2h+1⌉⋅O(h)=O(n) T(n) = \sum_{h=0}^{\lfloor \log n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil \cdot O(h) = O(n)T(n)=h=0∑⌊logn⌋⌈2h+1n⌉⋅O(h)=O(n)

三、数据结构定义

typedefenum{MIN_HEAP,// 父节点 <= 子节点MAX_HEAP// 父节点 >= 子节点}HeapType;typedefstruct{int*data;// 动态数组intsize;// 当前元素数intcapacity;// 数组容量HeapType type;// 堆类型标识}Heap;

采用函数指针或宏定义实现比较逻辑的抽象，可以在编译期确定堆类型，避免运行时的分支判断开销。

四、关键算法实现

4.1 向上调整（Heapify Up）

插入操作将新元素置于数组末尾，随后沿父节点方向逐级比较、交换，直至满足堆性质。

staticvoidheapifyUp(Heap*h,intindex){while(index>0){intparent=PARENT(index);if(hasHigherPriority(h,h->data[index],h->data[parent])){SWAP(h->data[index],h->data[parent]);index=parent;}else{break;}}}

4.2 向下调整（Heapify Down）

删除堆顶时，将末尾元素移至堆顶后，从根节点开始与子节点比较，与优先级较高的子节点交换，直至叶子节点。

staticvoidheapifyDown(Heap*h,intindex){while(true){intleft=LEFT(index);intright=RIGHT(index);intpriority=index;if(left<h->size&&hasHigherPriority(h,h->data[left],h->data[priority]))priority=left;if(right<h->size&&hasHigherPriority(h,h->data[right],h->data[priority]))priority=right;if(priority==index)break;SWAP(h->data[index],h->data[priority]);index=priority;}}

4.3 Floyd建堆算法

与逐个插入的O(nlog⁡n)O(n \log n)O(nlogn)复杂度相比，Floyd算法通过自底向上的批量调整，将建堆复杂度优化至线性。

Heap*heapBuild(int*arr,intn,HeapType type){Heap*h=heapCreate(n>4?n:4,type);memcpy(h->data,arr,sizeof(int)*n);h->size=n;// 从最后一个非叶子节点开始向下调整for(inti=PARENT(n-1);i>=0;i--){heapifyDown(h,i);}returnh;}

五、堆排序的实现

堆排序是一种原地、不稳定排序算法，核心思想是：

将待排序数组构建为最大堆（升序）或最小堆（降序）
反复将堆顶元素与末尾元素交换，堆规模减一
对新的堆顶执行向下调整
重复步骤2-3直至堆为空

voidheapSort(int*arr,intn,bool ascending){HeapType type=ascending?MAX_HEAP:MIN_HEAP;Heap*h=heapBuild(arr,n,type);for(inti=n-1;i>=0;i--){heapPop(h,&arr[i]);}heapDestroy(h);}

堆排序的时间复杂度恒为O(nlog⁡n)O(n \log n)O(nlogn)，空间复杂度为O(1)O(1)O(1)（若采用原地建堆优化）。

六、工程实践要点

6.1 动态扩容策略

当容量不足时，采用倍增策略扩容，均摊插入复杂度仍为O(1)O(1)O(1)。

staticboolheapExpand(Heap*h){intnewCapacity=h->capacity*2;int*newData=realloc(h->data,sizeof(int)*newCapacity);if(!newData)returnfalse;h->data=newData;h->capacity=newCapacity;returntrue;}

6.2 删除任意位置元素

删除非堆顶元素时，用末尾元素填充被删位置，随后同时执行向上和向下调整，确保堆性质恢复。

boolheapRemoveAt(Heap*h,intindex,int*outValue){*outValue=h->data[index];h->data[index]=h->data[--h->size];// 双方向调整，仅需其中一个会生效heapifyUp(h,index);heapifyDown(h,index);returntrue;}