数据结构(邓俊辉)学习笔记】优先级队列 09——左式堆:合并算法

本文主要是介绍数据结构(邓俊辉)学习笔记】优先级队列 09——左式堆:合并算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. LeftHeap模板类
  • 2. 算法
  • 3. 实现
  • 4. 实例

1. LeftHeap模板类

接下来这节,来讨论左式堆的合并算法。再给出具体算法之前,首先要给出左式堆模板类的定义。
在这里插入图片描述

比如这就是一种可能的实现方式,可以看到,我们这里再次利用了 C++的多重继承,只不过与完全二叉堆不同,既然左式堆已经不再满足结构性,所有元素在物理上也不可能继续保持紧密的排列,因此继续从向量进行派生已经不合时宜,而实际上在这样的场合中,灵活地改用树形结构作为派生的基类则是一种更加高效的方法。同样地,这里依然需要以优先级队列接口为"神",而取代向量的二叉树则扮演着"形"的角色。

既然同样的派生自 PQ, 左式堆也自然地应该提供优先级队列的三个标准接口,而根据这里的实现方式,最大元总是始终对应于根节点。因此,为了取出最大元,我们只需将根节点的数据域返回即可。

接下来我们就可以通过外部函数的形式给出将两个左式堆合并的具体算法。

2. 算法

实际上,采用递归的模式,左式堆合并算法可以非常简明地描述并实现。
在这里插入图片描述
来看一个一般的场景,假设待合并两个堆,分别以 a 和 b 为根,并且假设在抵达递归基之前,它们的左右子堆都是存在的。

我们可以借助递归将 a、b两个堆合并的问题转化为这样一个问题:具体来说也就是我们需要将 a 的右子堆取出,并且递归的与刚才的堆 b 完成合并,合并所得的结果继续作为 a 的右子堆。

当然,为了保证 a 在此后继续满足左倾性,在这次合并返回之后,我们还需比较 a_L 与合并之后这个堆的 NPL 值,如果有必要,我们还需另二者互换位置。

没错,整个算法就是这样的简单明了,尽管它的实现还需要破费一些功夫。

3. 实现

现在,我们就来将刚才的算法原理兑现为具体的代码。
在这里插入图片描述
比如这就是一种可能的实现方式,可以看到这是一个递归式的算法。

作为递归基,总共有两种情况,对应于待合并的堆中至少一个为空的情况。事实上只要其中一个为空,我们就直接返回另一个即可。

因此,当算法执行到这一句的时候(第三句)可以确认两个堆都不是空的,此时我们要比较两个根节点在数值上的大小,如果有必要,应将二者互换名称。从而保证在数值上 a 总是不小于 b,以便在后续递归的合并过程中将 b 作为 a 的后代。

接下来是核心的一步,我们需要递归地将 a 的右子堆与 b 进行合并。得益于递归的机制,接下来我们就可以假设这次合并的确完成。

因此接下来我们要在 a 及其新的右子树之间建立起一个正确的连接。

在完成了这样的拓扑连接之后,我们还需要进一步的确认 a 满足左倾性。也就是说就 NPL 而言,如果当前的左子堆要小于已右子堆,则需要将二者互换位置,

最后我们还需要根据 NPL 的定义及时地更新 a 的 NPL 值。

至此算法方可顺利返回。

4. 实例

以下,就来通过一个具体的实例加深对左式堆合并算法的理解和领悟:
在这里插入图片描述
假设在这里,我们需要将一个规模为4的堆与另一规模为3的堆合并起来。

  1. 首先通过比较,我们能确认前者的树根在数值上要大于后者的树根,因此二者无需互换,我们分别称之为 a 和 b。

  2. 相应的,a 的右孩子也自然就是12,于是按照算法,我们将原先的问题转化为 a 的右子堆与 b 堆的合并问题。

  3. 在新的这个递归层次,我们依然需要比较两个子堆的根节点,因为在数值上15更大,所以此时我们应该将它们互换名称,将前者记作 b,而将后者记作 a。于是问题进而转化为这样的形式,也就是说将15这个堆与12这个堆进行合并。

  4. 既然此时的 a 是15,所以 a 的右子树也自然就是8,是按照算法的流程,问题进一步转化为子堆8与子堆12的合并问题。

  5. 同样,在经过一次数值上的比较之后,我们确认应该将二者互换名称。也就是说接下来我们应该将12作为 a,而将8作为 b。

  6. 此时 a 的右孩子为空,因此在再接下来的递归层之上,将直接返回节点8,并且将8作为12的右孩子。也就是说在此局部应该是这样。

    请特别注意,在这层能递归返回之前,还有一项非常重要的任务,你还记得吗?

是的,我们需要确认12 满足左倾性,实际上它这个时候恰恰并不满足,因为我们注意到,它当前的左子树为空,当然,只要留意了这个问题,它的解决并不困难,你也应该记得是怎么处理的——没错,令他的左右子堆互换位置,这是为什么我们会得到这样一个局部结构。

  1. 接下来,我们的递归返回到节点15,同样地,在此我们也需要核对这个节点的左倾性。那么此时它的两个孩子 NPL 值各是多少呢?是的,都应该是1。因此左倾性在这个节点上并没有受到破坏。
  2. 因此我们可以继续逆行而上,递归返回至全堆的根,也就是节点17。此时的17是否满足左倾性呢?我们查验一下它的左右孩子 NPL 值各是多少,你也不妨心算一下。没错,左孩子的 NPL 值为1,而右孩子为 2。也就是说此时的节点 17 恰恰违反了左倾性。
  3. 同样地,关键在于发现问题、解决问题并不困难,在这个情况下,我们也只需经过一次兑换,交换17这个节点的左右孩子,在节点17的左右孩子召唤之后,这个数据结构也就从整体上恢复成一个左式堆。

不要忘了,构成这个堆的成员不多不少,恰好都来自于最初待合并的两个子堆。也就是说,我们已经顺利地完成了这样一个合并的任务。

当然,通过这个实例也可以验证我们最初的设计目标:也就是整个的合并过程的确是围绕着右侧链来进行的。因此整个算法的时间复杂度也自然就不超过右侧链的长度,我们此前已经就此做出过界定,也就是说它在渐进意义下绝对不会超过 log(n), 这个结果再好不过了。

这篇关于数据结构(邓俊辉)学习笔记】优先级队列 09——左式堆:合并算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1101724

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码