一、什么是堆堆Heap是一种特殊的完全二叉树数据结构它满足堆属性对于最大堆每个节点的值都大于或等于其子节点的值对于最小堆每个节点的值都小于或等于其子节点的值。堆通常用于实现优先队列也是堆排序算法的基础。二、堆的特性完全二叉树堆总是一棵完全二叉树这意味着除了最后一层其他层都是满的且最后一层的节点都尽可能靠左排列。堆属性大堆父节点的值 ≥ 子节点的值根节点最大小堆父节点的值 ≤ 子节点的值根节点最小数组表示由于是完全二叉树堆通常用数组来存储可以节省指针空间且能快速定位父子节点。typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }Heap;三、堆的存储与索引关系假设数组索引从 0 开始父节点索引parent(i) (i - 1) / 2左子节点索引leftChild(i) 2 * i 1右子节点索引rightChild(i) 2 * i 2四、堆的基本操作1. 堆的初始化//堆的初始化 void HeapInit(Heap* hp) { assert(hp); hp-a NULL; hp-capacity hp-size 0; }2. 堆的销毁// 堆的销毁 void HeapDestory(Heap* hp) { assert(hp); free(hp-a); hp-a NULL; hp-capacity hp-size 0; }3. 堆的插入//交换两数 void Swap(HPDataType* a, HPDataType* b) { HPDataType temp *a; *a *b; *b temp; } //堆的向上调整算法 void AdjustUp(HPDataType* a,int child) { while (child 0) { int parent (child - 1) / 2; if (a[child] a[parent]) { Swap(a[child], a[parent]); child parent; } else { break; } } } // 堆的插入 void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp-size hp-capacity) { int newcapacity hp-capacity 0 ? 4 : 2 * hp-capacity; HPDataType* temp (HPDataType*)realloc(hp-a,sizeof(HPDataType) * newcapacity); if (temp NULL) { perror(realloc failed); return; } hp-a temp; hp-capacity newcapacity; } hp-a[hp-size] x; //插入数据之后使用向上调整算法调整堆 AdjustUp(hp-a,hp-size-1); }4.堆的删除//堆的向下调整算法 void AdjustDown(HPDataType* a, int size,int parent) { //假设左孩子大 int child 2 * parent 1; while (child size) { if (child 1 size a[child] a[child 1]) child; if (a[parent] a[child]) { Swap(a[parent], a[child]); parent child; child 2 * parent 1; } else break; } } // 堆的删除堆顶数据 void HeapPop(Heap* hp) { assert(hp); assert(hp-size 0); Swap((hp-a[0]), (hp-a[hp-size - 1])); hp-size--; AdjustDown(hp-a, hp-size,0); }5.取堆顶的数据// 取堆顶的数据 HPDataType HeapTop(Heap* hp) { assert(hp); return hp-a[0]; }6.堆的数据个数// 堆的数据个数 int HeapSize(Heap* hp) { assert(hp); return hp-size; }7.堆的判空// 堆的判空 bool HeapEmpty(Heap* hp) { assert(hp); return hp-size 0; }五、堆的向上向下调整算法向上调整AdjustUp和向下调整AdjustDown是维护堆属性的两个核心算法它们保证了在插入或删除元素后堆的结构依然满足最大堆或最小堆的性质。1. 向上调整算法AdjustUp应用场景向堆中插入一个新元素后将其调整到正确位置以恢复堆属性。基本原理将新元素插入到数组末尾即完全二叉树的最后一个节点。比较该节点与其父节点的值若是最大堆且子节点值大于父节点值则交换两者若是最小堆且子节点值小于父节点值则交换两者。将当前节点更新为父节点重复步骤 2直到满足堆属性即不再需要交换或到达根节点。时间复杂度O(log n)因为最坏情况下需要从叶子节点一直交换到根节点而完全二叉树的高度为 log n。//交换两数 void Swap(HPDataType* a, HPDataType* b) { HPDataType temp *a; *a *b; *b temp; } //堆的向上调整算法 void AdjustUp(HPDataType* a,int child) { while (child 0) { int parent (child - 1) / 2; if (a[child] a[parent]) { Swap(a[child], a[parent]); child parent; } else { break; } } }2. 向下调整算法AdjustDown应用场景删除堆顶元素或替换堆顶元素后将新的堆顶元素下沉到正确位置以恢复堆属性。基本原理将堆顶元素与最后一个元素交换然后删除最后一个元素即原堆顶。从新的堆顶开始比较其与左右子节点的值若是最大堆选择值较大的子节点如果该子节点值大于父节点值则交换若是最小堆选择值较小的子节点如果该子节点值小于父节点值则交换。将当前节点更新为交换后的子节点重复步骤 2直到满足堆属性或到达叶子节点。时间复杂度O(log n)同样因为最坏情况下需要从根节点下沉到叶子节点。//堆的向下调整算法 void AdjustDown(HPDataType* a, int size,int parent) { //假设左孩子大 int child 2 * parent 1; while (child size) { if (child 1 size a[child] a[child 1]) child; if (a[parent] a[child]) { Swap(a[parent], a[child]); parent child; child 2 * parent 1; } else break; } }3. 算法对比与总结特性向上调整AdjustUp向下调整AdjustDown触发时机插入新元素后删除堆顶元素后起始位置新插入的叶子节点堆顶根节点移动方向自底向上向根节点自顶向下向叶子节点比较对象与父节点比较与较大的或较小的子节点比较时间复杂度O(log n)O(log n)核心用途维护插入后的堆属性维护删除后的堆属性这两个算法是堆所有操作插入、删除、建堆、堆排序的基础理解它们的原理和实现是掌握堆数据结构的关键。六、堆排序算法步骤将待排序数组构建成最大堆升序。此时堆顶元素arr[0]是最大值将其与数组末尾元素交换。缩小堆的大小排除已排序的末尾元素对新的堆顶元素执行下沉操作恢复堆属性。重复步骤 2-3直到堆的大小为 1。// 堆排序 O(N * logN) // 冒泡排序 O(N^2) void HeapSort(int* a, int n) { // 降序建小堆 // 升序建大堆 // 向上调整建堆 O(N*logN) /*for (int i 1; i n; i) { AdjustUp(a, i); }*/ // 向下调整建堆 O(N) for (int i (n-1-1)/2; i0; i--) { AdjustDown(a, n, i); } int end n - 1; while (end 0) { Swap(a[0], a[end]); AdjustDown(a, end, 0); end--; } }七、堆 vs 二叉搜索树特性堆二叉搜索树BST主要用途快速获取最大/最小值优先队列快速查找、插入、删除任意元素查找任意元素O(n)O(log n)平衡时获取最大/最小值O(1)O(log n) 或 O(n)结构要求完全二叉树满足堆属性左子树 根 右子树内存效率数组存储空间紧凑节点存储指针有额外开销八、总结堆是一种高效的数据结构特别适合需要频繁获取最大或最小元素的场景。它的完全二叉树特性和数组存储方式使得实现简单且空间效率高。掌握堆的基本操作和堆排序算法对于理解优先队列、解决Top K问题以及优化算法性能都有重要意义。