南宁网络建站,自己做的网站别人,荆门网站建设电话咨询,黄岩区住房保障建设局网站【如无特别说明#xff0c;皆为最小二叉堆】 1 介绍 2 特性
结构性#xff1a;符合完全二叉树的结构有序性#xff1a;满足父节点小于子节点#xff08;最小化堆#xff09;或父节点大于子节点#xff08;最大化堆#xff09;
3 二叉堆的存储
顺序存储
二叉堆的有序…【如无特别说明皆为最小二叉堆】 1 介绍 2 特性
结构性符合完全二叉树的结构有序性满足父节点小于子节点最小化堆或父节点大于子节点最大化堆
3 二叉堆的存储
顺序存储
二叉堆的有序性可以很容易地通过下标来反映 4 堆中插入新元素
堆的插入是在具有最大序号的元素之后插入新的元素或结点否则将违反堆的结构性。如果新元素放入后没有违反堆的有序性那么操作结束。否则让该节点向父节点移动直到满足有序性或到达根节点。新节点的向上移动称为向上过滤 4.1 时间效率
最坏情况是O(logn) 【一直交换到根节点】平均情况过滤会提前结束。 有资料表明平均是2.6次比较因此元素平均上移1.6层。
5 推出操作DeQueue
当最小元素被删除时在根上出现了一个空结点。堆的大小比以前小1堆的结构性告诉我们最后一个结点应该删掉。如果最后一项可以放在此空结点中就把它放进去。然而这通常是不可能的必须玩与插入操作类似的“游戏”把某些项放入空结点然后移动空结点。 仅有的区别在于对DeQueue操作空结点是往下移动。 找到空结点的一个较小的子结点如果该儿子的值小于我们要放入的项则把该儿子放入空结点把空结点往下推一层 重复这个动作直到该项能被放入正确的位置。 5.1 时间复杂度
最坏情况下deQueue是一个对数时间的操作根据堆的有序性堆中最后一个结点的值一般都是比较大的。因此向下过滤很少有提前一或二层结束的所以deQueue操作平均也是对数时间
6 建堆
可以看成N次连续插入其时间应该是在O(NlogN)时间内完成 事实上在构造过程中我们并不关心每个元素加入后堆的状态我们关心的是N个元素全部加入后的最后状态最后的状态是要保证堆的有序性。至于中间过程中的有序性是否成立并不重要。有了这个前提后我们能将构造堆的时间复杂度降到ON 利用堆的递归定义 如果函数buildHeap可以将一棵完全二叉树调整为一个堆 那么只要对左子堆和右子堆递归调用buildHeap。至此我们能保证除了根结点外其余的地方都建立起了堆的有序性。然后对根结点调用向下过滤以创建堆的有序性如果我们以逆向层次的次序对结点调用向下过滤那么在向下过滤节点i时所有结点i的子孙都已经调用过向下过滤。 不需要对叶结点执行向下过滤从编号最大的非叶结点开始向下过滤
6.1 举例 一开始根据数据的先后建立一棵完全二叉树 从序号最大的非叶子节点30开始进行向下过滤 6.2 时间分析 为h的节点叶节点高度为0在向下过滤中交换的最大次数是h建堆的最大时间是所有节点的调整时所需交换次数之和即所有节点的高度之和 7 D堆
每个节点有d个儿子这样生成的堆比较矮。插入删除需要在d个元素中找出最小的时间复杂度为优点插入快缺点删除慢用途 插入比删除多的队列队列太大内存放不下要放在外存的时候
