完全二叉树与堆底层原理深度剖析 | 手写C++大顶堆实现

完全二叉树与堆底层原理深度剖析 | 手写C大顶堆实现前言 一、前置基石完全二叉树深度解析1.1 完全二叉树数组存储的底层逻辑1.2 节点编号映射公式规则① 编号从 1 开始规则② 编号从 0 开始编程数组常用1.3 字符图解数组与完全二叉树映射树形逻辑结构对应一维数组存储⛰️ 二、堆的定义与核心性质拆解2.1 堆的本质定义2.2 堆中极值分布规律进阶极值位置分析 三、堆元素插入 向上上浮调整3.1 插入规则3.2 上浮调整原理大顶堆3.3 C 大顶堆插入 上浮核心代码 四、堆顶弹出 向下下沉调整4.1 堆弹出规则4.2 下沉调整原理大顶堆4.3 C 堆弹出 下沉完整代码 五、数据结构终极核心心法 六、知识点总结前言在编程算法的江湖里堆绝对是不可或缺的核心数据结构无论是堆排序、优先队列、TopK 问题求解背后都离不开堆的支撑。而堆并非凭空诞生它深度依附于完全二叉树二者有着密不可分的羁绊。很多同学学堆只记操作、不懂底层逻辑上手写代码一头雾水。今天带你由浅入深从完全二叉树底层逻辑出发层层拆解堆的定义、性质、元素插入、堆顶弹出、上浮 / 下沉调整原理搭配字符图解 可直接运行的 C 源码彻底吃透堆的核心精髓打通数据结构思维壁垒 一、前置基石完全二叉树深度解析1.1 完全二叉树数组存储的底层逻辑完全二叉树最大的特性可以用一段连续的一维数组完成存储无需像普通二叉树那样存储指针、浪费空间。究其根本完全二叉树的父节点与子节点编号存在固定数学映射关系节点之间排布紧凑、无空缺空位天然适配连续数组存储。我们要建立一种顶级编程思维逻辑层面是二维树形结构存储层面是一维数组结构高手看数组眼中自动映射出树形结构新手看数组只看到一串数字。1.2 节点编号映射公式设定父节点编号为i ii分两种编号规则规则① 编号从 1 开始左孩子编号b o l d s y m b o l 2 i boldsymbol{2i}boldsymbol2i右孩子编号b o l d s y m b o l 2 i 1 boldsymbol{2i1}boldsymbol2i1父节点编号b o l d s y m b o l i / 2 boldsymbol{i/2}boldsymboli/2整数除法规则② 编号从 0 开始编程数组常用左孩子编号b o l d s y m b o l 2 i 1 boldsymbol{2i1}boldsymbol2i1右孩子编号b o l d s y m b o l 2 i 2 boldsymbol{2i2}boldsymbol2i2父节点编号b o l d s y m b o l ( i − 1 ) / 2 boldsymbol{(i-1)/2}boldsymbol(i−1)/2整数除法1.3 字符图解数组与完全二叉树映射示例数组[5,6,3,2,1,9,8,12,11]树形逻辑结构5 / 6 3 / / 2 1 9 8 / 12 11对应一维数组存储下标0 1 2 3 4 5 6 7 8 数值5 6 3 2 1 9 8 12 11二者信息完全等价只是逻辑视图和存储视图的区别这是学习堆必须建立的直觉思维。⛰️ 二、堆的定义与核心性质拆解2.1 堆的本质定义堆是特殊的完全二叉树在完全二叉树结构基础上额外增加了父子节点大小约束规则分为两大类大顶堆最大堆树中任意父节点值 左右子节点值小顶堆最小堆树中任意父节点值 左右子节点值核心规律只约束父子节点大小关系兄弟节点之间无任何大小约束可随意交换位置且不破坏堆结构。2.2 堆中极值分布规律大顶堆全局最大值一定在堆顶根节点小顶堆全局最小值一定在堆顶根节点进阶极值位置分析以大顶堆为例第二大值只会出现在根节点的左孩子 或 右孩子第三大值可能出现在第二层 或 第三层所有节点第四大值可能分布在第二层、第三层、第四层原理很简单只有父子有大小层级横向兄弟无约束层级越靠下节点越有可能成为次大值。字符简易示意根(第1层) 最大值 / 左子(2层) 右子(2层) 第二大候选 / / 3层节点 3层节点 第三大候选 三、堆元素插入 向上上浮调整3.1 插入规则堆是完全二叉树必须遵守完全二叉树的排布规则新元素默认添加在完全二叉树最后一层最左侧映射到数组直接追加到数组末尾插入后大概率会破坏大顶堆 / 小顶堆的性质因此需要向上上浮调整重新维护堆的规则。3.2 上浮调整原理大顶堆将新元素放在数组末尾循环将当前节点与父节点比较若当前节点 父节点交换二者位置持续向上比对直到满足堆性质 或 到达堆顶3.3 C 大顶堆插入 上浮核心代码#includeiostream#includevectorusingnamespacestd;classMaxHeap{private:vectorintheap;// 向上上浮调整voidupAdjust(intidx){// 找到父节点下标while(idx0){intparent(idx-1)/2;// 子节点小于等于父节点无需调整if(heap[idx]heap[parent])break;// 交换父子节点swap(heap[idx],heap[parent]);// 向上继续比对idxparent;}}public:// 堆中插入元素voidpush(intval){heap.push_back(val);// 从最后一个元素开始上浮调整upAdjust(heap.size()-1);}// 获取堆顶元素inttop(){returnheap.empty()?-1:heap[0];}// 判断堆是否为空boolempty(){returnheap.empty();}};intmain(){MaxHeap hp;// 批量插入元素hp.push(5);hp.push(6);hp.push(3);hp.push(12);cout大顶堆堆顶最大值hp.top()endl;return0;} 四、堆顶弹出 向下下沉调整4.1 堆弹出规则堆的弹出操作只弹出堆顶元素大顶堆弹最大值小顶堆弹最小值。弹出后规则不能直接删除堆顶会破坏完全二叉树连续存储特性用数组最后一个元素覆盖堆顶空位数组长度减一舍弃末尾无效元素从堆顶开始向下下沉调整重新维护堆性质4.2 下沉调整原理大顶堆以当前根节点为基准找到左右子节点中的最大值若当前节点 最大子节点交换位置往下一层继续比对直到满足堆性质 或 到达叶子节点4.3 C 堆弹出 下沉完整代码在上面MaxHeap类中追加以下方法// 向下下沉调整voiddownAdjust(intidx){intnheap.size();while(true){intleft2*idx1;// 左孩子intright2*idx2;// 右孩子intmaxPosidx;// 找三者最大值下标if(leftnheap[left]heap[maxPos])maxPosleft;if(rightnheap[right]heap[maxPos])maxPosright;// 当前节点已是最大无需调整if(maxPosidx)break;swap(heap[idx],heap[maxPos]);// 下沉到最大值位置继续调整idxmaxPos;}}// 弹出堆顶元素voidpop(){if(heap.empty())return;// 末尾元素覆盖堆顶heap[0]heap.back();// 删除末尾元素heap.pop_back();// 从堆顶开始下沉调整downAdjust(0);} 五、数据结构终极核心心法学完堆的所有操作我们可以领悟所有数据结构的通用本质数据结构 定义结构性质 代码操作维护性质结构定义规定数据结构长什么样、具备什么约束规则堆是完全二叉树 父子节点大小规则队列先进先出、队尾入队队头出队结构操作插入、删除、查找等操作最终目的都是维护既定性质堆插入上浮、弹出下沉都是为了不破坏大 / 小顶堆规则队列不允许头部入队否则就失去队列本身的性质学习数据结构不要死记代码、死背步骤先理解性质再理解如何维护性质一通百通所有数据结构都能快速上手。 六、知识点总结完全二叉树是堆的底层载体可通过固定公式实现数组与树形映射堆分为大顶堆、小顶堆仅约束父子大小兄弟无大小关系插入走末尾追加 向上上浮弹出走末尾补位 向下下沉上浮从下往上比对父节点下沉从上往下比对子节点最大值数据结构核心思想定义规则用操作维护规则。