【数据结构与算法】第44篇：堆（Heap）的实现

目录一、堆的基本概念1.1 堆的定义1.2 堆 vs 堆区1.3 应用场景二、堆的实现大根堆2.1 结构定义2.2 初始化与销毁2.3 辅助函数交换与扩容2.4 上浮操作用于插入2.5 插入操作2.6 下沉操作用于删除最大值2.7 删除最大值弹出堆顶2.8 获取堆顶不删除2.9 获取堆大小三、完整代码演示四、堆排序基于堆实现五、小根堆的实现六、复杂度分析七、堆的应用Top K 问题八、小结九、思考题一、堆的基本概念1.1 堆的定义堆是一种完全二叉树分为两种大根堆每个节点的值 ≥ 左右孩子节点的值小根堆每个节点的值 ≤ 左右孩子节点的值用数组存储下标从0开始节点 i 的左孩子2*i 1节点 i 的右孩子2*i 2节点 i 的父节点(i - 1) / 21.2 堆 vs 堆区概念含义说明堆数据结构一种树形结构用于优先队列本章讨论的内容堆区内存程序运行时动态分配内存的区域malloc/free 管理的区域两者是完全不同的概念只是名字相同。1.3 应用场景场景说明优先队列每次取出优先级最高的元素堆排序O(n log n) 排序Top K 问题找最大/最小的K个元素合并 K 个有序链表用堆选择最小值二、堆的实现大根堆2.1 结构定义c#include stdio.h #include stdlib.h #include string.h #define INIT_CAPACITY 10 typedef struct { int *data; // 动态数组 int size; // 当前元素个数 int capacity; // 数组容量 } MaxHeap;2.2 初始化与销毁cvoid initHeap(MaxHeap *heap) { heap-data (int*)malloc(INIT_CAPACITY * sizeof(int)); heap-size 0; heap-capacity INIT_CAPACITY; } void destroyHeap(MaxHeap *heap) { free(heap-data); heap-data NULL; heap-size 0; heap-capacity 0; }2.3 辅助函数交换与扩容cvoid swap(int *a, int *b) { int temp *a; *a *b; *b temp; } void resize(MaxHeap *heap) { heap-capacity * 2; heap-data (int*)realloc(heap-data, heap-capacity * sizeof(int)); }2.4 上浮操作用于插入新插入的元素放在数组末尾然后向上调整直到满足堆性质。cvoid shiftUp(MaxHeap *heap, int index) { while (index 0) { int parent (index - 1) / 2; if (heap-data[parent] heap-data[index]) { break; } swap(heap-data[parent], heap-data[index]); index parent; } }2.5 插入操作cvoid push(MaxHeap *heap, int value) { if (heap-size heap-capacity) { resize(heap); } heap-data[heap-size] value; shiftUp(heap, heap-size); heap-size; }2.6 下沉操作用于删除最大值删除堆顶后将最后一个元素放到堆顶然后向下调整。cvoid shiftDown(MaxHeap *heap, int index) { while (index * 2 1 heap-size) { int left index * 2 1; int right index * 2 2; int largest left; if (right heap-size heap-data[right] heap-data[left]) { largest right; } if (heap-data[index] heap-data[largest]) { break; } swap(heap-data[index], heap-data[largest]); index largest; } }2.7 删除最大值弹出堆顶cint pop(MaxHeap *heap) { if (heap-size 0) { printf(堆为空\n); return -1; } int maxVal heap-data[0]; heap-data[0] heap-data[heap-size - 1]; heap-size--; shiftDown(heap, 0); return maxVal; }2.8 获取堆顶不删除cint top(MaxHeap *heap) { if (heap-size 0) { printf(堆为空\n); return -1; } return heap-data[0]; }2.9 获取堆大小cint size(MaxHeap *heap) { return heap-size; } int isEmpty(MaxHeap *heap) { return heap-size 0; }三、完整代码演示c#include stdio.h #include stdlib.h #define INIT_CAPACITY 10 typedef struct { int *data; int size; int capacity; } MaxHeap; void initHeap(MaxHeap *heap) { heap-data (int*)malloc(INIT_CAPACITY * sizeof(int)); heap-size 0; heap-capacity INIT_CAPACITY; } void destroyHeap(MaxHeap *heap) { free(heap-data); heap-data NULL; heap-size 0; heap-capacity 0; }void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } void resize(MaxHeap *heap) { heap-capacity * 2; heap-data (int*)realloc(heap-data, heap-capacity * sizeof(int)); } void shiftUp(MaxHeap *heap, int index) { while (index 0) { int parent (index - 1) / 2; if (heap-data[parent] heap-data[index]) { break; } swap(heap-data[parent], heap-data[index]); index parent; } } void shiftDown(MaxHeap *heap, int index) { while (index * 2 1 heap-size) { int left index * 2 1; int right index * 2 2; int largest left; if (right heap-size heap-data[right] heap-data[left]) { largest right; } if (heap-data[index] heap-data[largest]) { break; } swap(heap-data[index], heap-data[largest]); index largest; } } void push(MaxHeap *heap, int value) { if (heap-size heap-capacity) { resize(heap); } heap-data[heap-size] value; shiftUp(heap, heap-size); heap-size; } int pop(MaxHeap *heap) { if (heap-size 0) { printf(堆为空\n); return -1; } int maxVal heap-data[0]; heap-data[0] heap-data[heap-size - 1]; heap-size--; shiftDown(heap, 0); return maxVal; } int top(MaxHeap *heap) { if (heap-size 0) { printf(堆为空\n); return -1; } return heap-data[0]; } int size(MaxHeap *heap) { return heap-size; } int isEmpty(MaxHeap *heap) { return heap-size 0; } void printHeap(MaxHeap *heap) { printf(堆内容数组形式: ); for (int i 0; i heap-size; i) { printf(%d , heap-data[i]); } printf(\n); } int main() { MaxHeap heap; initHeap(heap); printf( 插入元素 \n); int values[] {10, 20, 15, 30, 40, 25, 5}; for (int i 0; i 7; i) { push(heap, values[i]); printf(插入 %d 后堆顶: %d\n, values[i], top(heap)); } printHeap(heap); printf(堆大小: %d\n, size(heap)); printf(\n 弹出元素 \n); while (!isEmpty(heap)) { int val pop(heap); printf(弹出: %d, 剩余堆大小: %d\n, val, size(heap)); } destroyHeap(heap); return 0; }运行结果text 插入元素 插入 10 后堆顶: 10 插入 20 后堆顶: 20 插入 15 后堆顶: 20 插入 30 后堆顶: 30 插入 40 后堆顶: 40 插入 25 后堆顶: 40 插入 5 后堆顶: 40 堆内容数组形式: 40 30 25 10 20 15 5 堆大小: 7 弹出元素 弹出: 40, 剩余堆大小: 6 弹出: 30, 剩余堆大小: 5 弹出: 25, 剩余堆大小: 4 弹出: 20, 剩余堆大小: 3 弹出: 15, 剩余堆大小: 2 弹出: 10, 剩余堆大小: 1 弹出: 5, 剩余堆大小: 0四、堆排序基于堆实现cvoid heapSort(int arr[], int n) { MaxHeap heap; initHeap(heap); // 建堆 for (int i 0; i n; i) { push(heap, arr[i]); } // 从大到小输出大根堆弹出最大值 for (int i n - 1; i 0; i--) { arr[i] pop(heap); } destroyHeap(heap); } int main() { int arr[] {3, 5, 1, 8, 2, 9, 4, 7, 6}; int n sizeof(arr) / sizeof(arr[0]); printf(原数组: ); for (int i 0; i n; i) printf(%d , arr[i]); printf(\n); heapSort(arr, n); printf(排序后: ); for (int i 0; i n; i) printf(%d , arr[i]); printf(\n); return 0; }运行结果text原数组: 3 5 1 8 2 9 4 7 6 排序后: 1 2 3 4 5 6 7 8 9五、小根堆的实现将大根堆的shiftUp和shiftDown中的比较符号反转即可。c// 小根堆的上浮 void shiftUpMin(MaxHeap *heap, int index) { while (index 0) { int parent (index - 1) / 2; if (heap-data[parent] heap-data[index]) { // 父 ≤ 子则停止 break; } swap(heap-data[parent], heap-data[index]); index parent; } } // 小根堆的下沉 void shiftDownMin(MaxHeap *heap, int index) { while (index * 2 1 heap-size) { int left index * 2 1; int right index * 2 2; int smallest left; if (right heap-size heap-data[right] heap-data[left]) { smallest right; } if (heap-data[index] heap-data[smallest]) { break; } swap(heap-data[index], heap-data[smallest]); index smallest; } }六、复杂度分析操作时间复杂度说明插入pushO(log n)上浮最多树高次删除最大值popO(log n)下沉最多树高次取堆顶topO(1)直接返回数组[0]建堆heapifyO(n)从最后一个非叶子节点下沉七、堆的应用Top K 问题找数组中最大的 K 个元素用小根堆实现 O(n log K)。cint* findTopK(int arr[], int n, int k) { if (k 0 || k n) return NULL; MaxHeap minHeap; // 实际用小根堆 // 注意这里用大根堆取负值模拟小根堆或单独实现小根堆 // 简化版先插入k个元素 // 然后遍历剩余元素比堆顶大则替换 // 完整实现略原理相同 }八、小结这一篇我们实现了基于动态数组的大根堆操作函数核心算法插入push上浮shiftUp删除最大值pop下沉shiftDown取堆顶topO(1)关键点堆是完全二叉树用数组存储大根堆父 ≥ 子堆顶最大上浮新元素在末尾向上比较交换下沉堆顶元素被删除末尾元素补上向下比较交换注意区分数据结构堆本文树形结构优先队列内存堆区malloc 管理的内存区域下一篇我们讲跳跃表Skip List。九、思考题为什么堆用数组存储而不需要显式的左右指针建堆时为什么从最后一个非叶子节点开始向下调整而不是从根开始如何用堆实现一个优先队列支持按优先级取出元素堆排序的空间复杂度是 O(1)本文的堆排序用了 O(n) 额外空间如何优化欢迎在评论区讨论你的答案。