堆这个结构特别有意思。很多人第一次学它时会产生一种轻微错乱感说它是树实现却经常用数组结果一转眼又去做排序和 TopK 了于是就会感觉这玩意儿到底是树还是数组还是排序工具其实这三层身份它都有。而堆最有价值的地方恰恰就在这里它把“树结构的优先级关系”和“数组存储的高效实现”结合到了一起。所以堆不是一章孤立的内容。它是树、数组、排序、TopK 这些内容之间的一座桥。仓库位置D:\Users\30335\c技术栈学习\data-structure\堆核心文件Heap.hHeap.cTest.c一、堆到底是什么堆本质上是一棵完全二叉树并且满足某种额外顺序约束。最常见的有两种大堆父结点大于等于孩子结点。小堆父结点小于等于孩子结点。仓库里的实现更接近小堆逻辑。你看AdjustUp和AdjustDown的判断条件就能看出来if(a[child]a[parent])这意味着更小的元素会往上走。所以堆的第一层本质可以记成一句话堆不是普通二叉树它是一棵带优先级秩序的完全二叉树。二、为什么堆明明是树却经常用数组实现这是很多人第一次接触堆时最困惑的地方之一。原因其实很简单堆是完全二叉树而完全二叉树特别适合顺序存储。如果用数组表示完全二叉树父子结点下标之间有很稳定的关系左孩子2 * parent 1右孩子2 * parent 2父结点(child - 1) / 2这就意味着不需要真的开一个“树结点结构”也不需要显式保存左右指针只用数组就能把树关系算出来这就是堆为什么特别“像树又像数组”。说得更直白一点堆的逻辑结构是树物理结构通常是数组。三、堆结构在代码里长什么样仓库里的堆结构如下typedefstructHeap{HPDataType*a;intsize;intcapacity;}HP;这三个成员的作用非常直接a底层数组size当前有效元素个数capacity当前容量你会发现这和顺序表的结构其实非常像。这也再次说明堆虽然是树但它的工程实现风格很多时候非常像“带规则的动态数组”。四、堆最核心的不是接口而是两种调整动作学堆时最值得真正吃透的不是“函数名”而是这两个动作向上调整AdjustUp向下调整AdjustDown它们几乎决定了堆的一切行为。1. 向上调整仓库代码voidAdjustUp(HPDataType*a,intchild){intparent(child-1)/2;while(child0){if(a[child]a[parent]){Swap(a[child],a[parent]);childparent;parent(child-1)/2;}else{break;}}}这个过程特别像新元素刚进来如果它比父结点更“应该待在上面”那就不断往上换。2. 向下调整仓库代码voidAdjustDown(HPDataType*a,intn,intparent){intchild2*parent1;while(childn){if(child1na[child]a[child1]){child;}if(a[child]a[parent]){Swap(a[child],a[parent]);parentchild;child2*parent1;}else{break;}}}这个过程则像顶部元素掉下来以后如果它已经不配待在这个位置就继续往下面沉。这两个动作一旦看懂堆就不再神秘了。五、入堆和出堆为什么刚好一上一下入堆HPPushvoidHPPush(HP*php,HPDataType x){assert(php);if(php-sizephp-capacity){intnewcapacityphp-capacity0?4:php-capacity*2;HPDataType*newnode(HPDataType*)realloc(php-a,newcapacity*sizeof(HPDataType));if(newnodeNULL){perror(realloc fail!);exit(1);}php-anewnode;php-capacitynewcapacity;}php-a[php-size]x;AdjustUp(php-a,php-size-1);}思路非常典型先把新元素放到数组末尾然后做一次向上调整出堆HPPopvoidHPPop(HP*php){assert(php);assert(php-size0);Swap(php-a[0],php-a[php-size-1]);php-size--;AdjustDown(php-a,php-size,0);}思路则是把堆顶和最后一个元素交换缩小有效区间从堆顶开始向下调整所以入堆靠“上浮”出堆靠“下沉”这是堆这一章最应该形成的动作感。六、为什么堆顶永远这么重要因为堆的存在意义本来就是为了让堆顶变得“有价值”。在小堆里堆顶永远最小在大堆里堆顶永远最大所以仓库中的HPTop()HPDataTypeHPTop(HP*php){assert(phpphp-size0);returnphp-a[0];}看起来只是取数组第一个元素但它背后代表的是我可以在不遍历全体的情况下快速拿到当前优先级最高的元素。这就是堆和普通数组最大的不同。七、建堆为什么比你想象中更讲究仓库里的HeapSort给了两种建堆思路1. 一个个插入再一路向上调整这种思路简单但整体成本更高。2. 从最后一个非叶子结点开始向下调整建堆for(inti(n-1-1)/2;i0;i--){AdjustDown(a,n,i);}这就是经典的“向下调整建堆”。它之所以重要是因为它让你第一次明显感受到同样都是“建堆”不同过程设计整体效率会有明显差别。这也是数据结构很有意思的一点不是只有“结果对不对”还要看“路径划不划算”。八、堆排序为什么天然和堆绑定仓库里的堆排序逻辑很清楚voidHeapSort(HPDataType*a,intn){for(inti(n-1-1)/2;i0;i--){AdjustDown(a,n,i);}intendn-1;while(end0){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}}它的本质是先把数组整理成堆每次把堆顶放到最终位置再对剩余部分继续维持堆结构这其实就是在不断做一件事每轮都先把“当前最该先出去的元素”拿出来。所以堆排序不是“硬套了一个堆结构”而是堆的优先级特性在排序上的自然展开。九、TopK 为什么总和堆绑在一起出现仓库里的TestHeap3()就是一个很典型的 TopK 思路。它的核心过程是先取前k个数据建一个小堆后续每来一个新数据就和堆顶比较如果新数据更大就替换堆顶并向下调整这一套为什么高效因为堆顶始终代表当前这k个候选值里“最该被踢出去”的那个。所以 TopK 真正用堆的地方不只是“维护一组数”而是利用堆快速维护一个动态的优先级边界。这也是堆为什么特别适合选择问题。十、堆这一章最容易写错的地方初学堆的时候最容易翻车的通常不是大方向而是这些细节1. 父子下标公式写错这是基础中的基础。2.AdjustDown里左右孩子比较顺序没理清尤其是你要维护小堆还是大堆一定要统一。3. 出堆时忘记先交换再缩小区间4. 堆排序时把有效区间和总区间混了5. TopK 场景里大小堆选反了比如求最大的前 K 个元素常常是维护一个小堆因为堆顶才好作为“当前最小门槛”。这些细节都不复杂但特别容易让实现跑偏。十一、堆这一章真正该建立的感觉我觉得堆真正值得学会的不只是代码而是下面这种结构意识通过维护局部有序关系可以非常高效地拿到全局当前最重要的那个元素。这是堆和很多普通结构最大的差别。它不追求全局完全有序但它特别擅长保证堆顶一定对后续调整成本可控这种“局部规则撑起整体高效”的思想非常经典。复习时只看这几句就够了堆是满足堆序性质的完全二叉树堆常用数组实现因为完全二叉树适合顺序存储入堆的核心是向上调整出堆的核心是向下调整堆顶始终是当前优先级最高的元素堆排序和 TopK 都是堆的经典应用学堆时最重要的不是背代码而是理解“优先级维护”这件事