已阅读5页,还剩26页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
Pairing Heaps,Actual Complexity,Pairing Heaps,Amortized Complexity,Pairing Heaps,Experimental results suggest that pairing heaps are actually faster than Fibonacci heaps. Simpler to implement. Smaller runtime overheads. Less space per node.,Definition,A min (max) pairing heap is a min (max) tree in which operations are done in a specified manner.,Node Structure,Child Pointer to first node of children list. Left and Right Sibling Used for doubly linked linked list (not circular) of siblings. Left pointer of first node is to parent. x is first node in list iff x.left.child = x. Data Note: No Parent, Degree, or ChildCut fields.,Meld Max Pairing Heap,Compare-Link Operation Compare roots. Tree with smaller root becomes leftmost subtree.,+,=,Actual cost = O(1).,Insert,Create 1-element max tree with new item and meld with existing max pairing heap.,+,insert(2),=,Insert,Create 1-element max tree with new item and meld with existing max pairing heap.,+,insert(14),=,Actual cost = O(1).,Worst-Case Degree,Insert 9, 8, 7, , 1, in this order.,Worst-case degree = n 1.,Worst-Case Height,Insert 1, 2, 3, , n, in this order.,Worst-case height = n.,IncreaseKey(theNode, theAmount),Since nodes do not have parent fields, we cannot easily check whether the key in theNode becomes larger than that in its parent. So, detach theNode from sibling doubly-linked list and meld.,IncreaseKey(theNode, theAmount),If theNode is not the root, remove subtree rooted at theNode from its sibling list.,IncreaseKey(theNode, theAmount),Meld subtree with remaining tree.,1,2,6,9,2,18,3,3,IncreaseKey(theNode, theAmount),2,18,3,3,Actual cost = O(1).,Remove Max,If empty = fail. Otherwise, remove tree root and meld subtrees into a single max tree. How to meld subtrees? Good way = O(log n) amortized complexity for remove max. Bad way = O(n) amortized complexity.,Bad Way To Meld Subtrees,currentTree = first subtree. for (each of the remaining trees) currentTree = compareLink(currentTree, nextTree);,Example,Remove max.,Meld into one tree.,Example,Actual cost of insert is 1. Actual cost of remove max is degree of root. n/2 inserts (9, 7, 5, 3, 1, 2, 4, 6, 8) followed by n/2 remove maxs. Cost of inserts is n/2. Cost of remove maxs is 1 + 2 + + n/2 1 = Q(n2). If amortized cost of an insert is O(1), amortized cost of a remove max must be Q(n).,Good Ways To Meld Subtrees,Two-pass scheme. Multipass scheme. Both have same asymptotic complexity. Two-pass scheme gives better observed performance.,Two-Pass Scheme,Pass 1. Examine subtrees from left to right. Meld pairs of subtrees, reducing the number of subtrees to half the original number. If # subtrees was odd, meld remaining original subtree with last newly generated subtree. Pass 2. Start with rightmost subtree of Pass 1. Call this the working tree. Meld remaining subtrees, one at a time, from right to left, into the working tree.,Two-Pass Scheme Example,Pass 1,Two-Pass Scheme Example,Pass 2,Multipass Scheme,Place the subtrees into a FIFO queue. Repeat until 1 tree remains. Remove 2 subtrees from the queue. Meld them. Put the resulting tree onto the queue.,Multipass Scheme Example,Multipass Scheme-Example,Multipass Scheme-Example,Actual cost = O(n).,Remove Nonroot Element,Remove theNode from its sibling list. Meld children of theNode using either 2-pass or multipass scheme. Meld resulting tree with whats left of original tree.,Remove(theNode),Remove theNode from its doubly-linked sibling list.,Remove(theNode),Meld children of theNode.,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年大学计算机基础考试题库及答案【新】
- 2024年大学计算机基础考试题库有完整答案
- 广东省惠州市华罗庚中学2024届高考数学二模试卷含解析
- 河南省商丘市九校2024年高三第二次模拟考试数学试卷含解析
- BYJ80-35D(170K)不压井作业机说明书
- 2023-2024学年陕西省周至县第五中学高考考前提分数学仿真卷含解析
- 施工合同管理控制项目造价研究论文
- 2024届山东省枣庄市高三上学期期末考试物理及答案
- 广东省揭阳市普宁市2024届中考二模化学试题含解析
- 2024届安徽省合肥市滨湖区重点中学中考押题化学预测卷含解析
- MT-T 1201.1-2023 煤矿感知数据联网接入规范 第1部分:安全监控
- 胎盘早剥应急预案演练脚本
- 《战锤 荷鲁斯之乱 荷鲁斯崛起 战锤系列 》读书笔记思维导图
- 中国航天日扬帆起航逐梦九天(课件)-小学主题班会通用版
- 2023年中智总部及直属单位个高管职位公开招聘笔试参考题库附带答案详解
- 新冀少版七年级下册生物全册知识点清单
- 电影鉴赏(山东联盟)智慧树知到答案章节测试2023年中国海洋大学
- 餐饮五常管理
- 茶艺与茶文化智慧树知到答案章节测试2023年石家庄信息工程职业学院
- 4G-5G异系统互操作
- 祖母的呼唤 牛汉
评论
0/150
提交评论