数据结构(邓俊辉)学习笔记】优先级队列 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

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

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