网站策划书网站需求分析,看汽车哪个网站好,网站搜索引擎优化方案范文,seo综合查询国产【0】README
0.1#xff09; 本文总结于 数据结构与算法分析#xff0c;但源代码均为原创#xff1b;旨在理清二叉堆#xff08;优先队列#xff09; 堆的其他操作及其应用#xff0c; 以便让朋友些知道为什么要学习优先队列#xff1b; 【1】二叉堆
1.0#xff09;…【0】README
0.1 本文总结于 数据结构与算法分析但源代码均为原创旨在理清二叉堆优先队列 堆的其他操作及其应用 以便让朋友些知道为什么要学习优先队列 【1】二叉堆
1.0优先队列定义优先队列是允许至少下列两种操作的数据结构insert插入 它的工作时显而易见的以及 deleteMin删除最小者 它的工作是找出、返回和删除优先队列中最小的元素 1.1我们把二叉堆中只叫做堆 堆也有两个性质结构性和堆序性对堆的 insert and deleteMin 操作必须要到堆的所有性质都被满足时才能终止 1.2结构性质 堆是一棵被完全填满的二叉树其底层上的元素从左到右填入这样的树称为 完全二叉树完全二叉树 的高是 logN(向下取整) 显然它是 OlogN 堆数据结构将由一个数组不管关键字是什么类型、一个代表最大值的整数及当前的堆大小组成
1.3 堆序性质
1堆序性使操作被快速执行的性质是 堆序性由于我们想要快速找出最小元因此最小元应该在根上依据树的递归定义则任意节点就应该小于它的后裔 【2】基本的堆操作
2.1insert 插入为将一个元素X 插入到堆中 在下一个空闲位置创建一个空穴 否则该堆将不是完全树如果X 可以放在该空穴中而并不破坏堆的序 那么插入完成 否则 我们把空穴的父节点上的元素移入该空穴中这种一般策略叫做 上滤 新元素在堆中上滤直到找出正确的位置 2.2deleteMin删除最小元找出最小元容易困难是删除它当删除一个最小元时 在根节点处产生了一个空穴 由于现在堆少了一个元素因此对中最后一个元素 X 必须移动到堆的某个地方如果X 可以被放到空穴中那么 deleteMin 完成显然这一般不可能 因此我们将空穴中的较小者移入空穴 这样就把空穴向下推了一层重复该步骤直到 X 可以被放入空穴中因此我们的做法是将 X 置入沿着从根开始包含最小儿子的 一条路径上的一个正确的位置这种策略叫做下滤 2.3出现的问题解决方法
出现的问题在堆实现中 经常发生的错误是当堆中存在偶数个元素的时候 此时将遇到一个节点只有一个儿子的情况 我们必须保证假设节点不总有两个儿子 解决方法始终保证你的算法把每一个节点都看成有两个儿子 【3】源代码printing
3.1download source code : https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter6 3.2代码详情打印效果参见 http://blog.csdn.net/PacosonSWJTU/article/details/49498255 的“【2】source codeprinting”部分因为二叉堆优先队列的基本操作 和 其他高级的应用操作的实现代码我都放到一起的
