左偏堆的特点及其应用_第1页
左偏堆的特点及其应用_第2页
左偏堆的特点及其应用_第3页
左偏堆的特点及其应用_第4页
左偏堆的特点及其应用_第5页
已阅读5页，还剩17页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、左侧部分树的特性和应用，广东省中山市第一中学黄元河、2、左侧部分树的定义，左侧部分树除支持优先级队列的三个基本操作(插入、删除、最小节点)外，还支持非常特殊的作业合并操作的一种并集(Mergeable Heap)左侧的部分树是“堆顺序”(Heap Ordered)二进制树。左侧部分树满足左侧部分的“Leftist Property(属性)”。3，左侧部分树定义左侧部分特性，左侧部分树的外部节点(外部节点)定义左侧或右侧子树为空的节点。节点I的距离(dist(i)是从节点I到其后代最近的外部节点通过的边数。任何节点的左侧子节点距离都不小于右侧子节点的距离(左侧部分属性)。如左侧部分属性所示，一个

2、节点的距离等于该节点为根的子树最右侧路径的长度。4，左侧部分树的特性，清理：如果左侧部分树中有N个节点，则左侧部分树的距离不会超过log(N 1) -1。最大右侧路径3360 ACG最大右侧路径节点数=3距离=2，8节点左侧部分树的最大距离：log(8 1) -1=2，5，左侧部分树操作，左侧部分树支持以下操作：MakeNull初始化左空部分树Merge。插入两个左侧部分树Insert新节点Min插入最小节点DeleteMin删除最小节点Delete删除所有已知节点Decrease减少一个节点的关键值，6，合并左侧部分树操作，合并操作递归。合并T1和T2的左侧子树，首先合并T1的右侧子树与T2

3、，合并左侧子树的操作，合并操作递归，合并操作递归，a，L1，R，T1的右侧子树与T2合并，8，合并左侧子树的操作，合并操作递归，左侧合并后，右侧子树大于左侧子树距离9，左侧子树的操作可能被合并。合并操作的代码如下：functionmerge (a，b)if a=NULL then return b if b=NULL then return a if key(b)dist(left(a)then sware、15、合并左侧部分树中的任务，以下是合并的示例：1、1、2、26、17、37、18、8、7、16、合并左侧部分树中的任务，17，合并左侧部分树中的操作。以下是合并的示例：3，10，2，0，1，18，合并左侧部分树中的任务。合并操作始终沿两个左侧部分树的最右侧路径执行。N个节点的左侧部分树，最右侧路径中最多包含log(N 1)节点。因此，合并操作的时间复杂性为O(log N1 log N2)=O(log N)，19，插入左侧树的操作，并将插入新节点的节点合并到单节点左侧部分树中的两个左侧部分树时间复杂性(O(log N)，20，)删除最小节点合并根节点左右子树时间复杂性：o (log n)，21，摘要，左侧

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论