重庆住房城乡建设厅网站首页,网站开发 开票,石油大学网页设计与网站建设,科技网站设计公司青铜挑战-堆结构
堆结构#xff1a;重要的基础数据结构
明确什么类型的题目可以用堆#xff0c;以及如何用堆来解决
堆的构造和维护过程都非常复杂
1.堆的概念与特征
1.1基本概念
堆#xff1a;是将一组数据按照 完全二叉树 的存储顺序#xff0c;将数据存储在一个一…青铜挑战-堆结构
堆结构重要的基础数据结构
明确什么类型的题目可以用堆以及如何用堆来解决
堆的构造和维护过程都非常复杂
1.堆的概念与特征
1.1基本概念
堆是将一组数据按照 完全二叉树 的存储顺序将数据存储在一个一维数组中的结构。
完全二叉树一棵深度为k的有n个结点的二叉树对树中的结点按从上至下、从左到右的顺序进行编号如果编号为i1≤i≤n的结点与满二叉树中编号为i的结点在二叉树中的位置相同则这棵二叉树称为完全二叉树。 堆有两种结构大顶堆、小顶堆其他叫法大根堆、小跟堆最大堆、最小堆 父子之间关系的建立节点下标为i
i0时为跟节点i1时父节点为(i-1)/2
1.2堆与优先队列
优先队列和堆不是一个同level的概念 Java的PriorityQueue就是堆实现的Java领域可以认为堆就是优先级队列优先级队列就是堆换做其他场景则不行
2.堆的构造过程
使用数组构造堆时先按照层次将所有元素依次填入二叉树中使其成为二叉树然后再不断调整最终使其符合堆结构
将元素依次排到完全二叉树节点上去找到下标为 (size-2)/2 4的节点i调整其位置满足堆性质找到i-1节点调整位置满足堆性质重复上述直到调整完跟节点
3.插入操作
插入规则
将元素插入到保持其为完全二叉树的最后一个位置然后顺着这条支路一直向上调整每前进一层就要保证其子树都满足堆否则就去处理子树直到完全满足要求
4.删除操作
堆本身比较特殊一般对堆中进行删除操作都是针对堆顶的元素
直接删除堆顶整个结构被破坏了实际策略是先将堆中的最后一个元素加入为A和堆顶元素进行替换然后删除堆中最后一个元素。 之后再从根开始逐步与左右比较谁更大谁上位。 然后A再继续与子树比较如果有更大的继续交换直到自己所在的子树也满足大顶堆
形象比喻 皇上突然驾崩了这时候先找个顾命大臣维持局面大臣先看左右两个皇子谁更强谁就是老大。然后大臣自己再逐步隐退直到找到属于自己的位置。
5.总结
堆的价值体现 大顶推的根节点是整个树最大的那个增加时会根据根的大小来决定要不要加删除操作只删除根元素。
为什么堆的效率比较高 堆元素的数量是有限制的一般不用将所有元素都放到堆里
后面题目中可以看到在序列中找k大则堆的大小就是k如果k个链表合并那么堆就是k。
堆的口诀 查找找大用小大的进找小用大小的进。 排序升序用小降序用大。
口诀解释 找K大则用小堆后序数据只有比根元素更大时才允许进入堆。 找K小则用大堆后序数据只有比根元素更小时才允许进入堆。
