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

相关文章

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Java中常见队列举例详解(非线程安全)

《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,:本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一.队列定义 二.常见接口 三.常见实现类3.1 ArrayDeque3.1.1 实现原理3.1.2

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》:本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

golang实现延迟队列(delay queue)的两种实现

《golang实现延迟队列(delayqueue)的两种实现》本文主要介绍了golang实现延迟队列(delayqueue)的两种实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录1 延迟队列:邮件提醒、订单自动取消2 实现2.1 simplChina编程e简单版:go自带的time

利用Python实现Excel文件智能合并工具

《利用Python实现Excel文件智能合并工具》有时候,我们需要将多个Excel文件按照特定顺序合并成一个文件,这样可以更方便地进行后续的数据处理和分析,下面我们看看如何使用Python实现Exce... 目录运行结果为什么需要这个工具技术实现工具的核心功能代码解析使用示例工具优化与扩展有时候,我们需要将

Python实现获取带合并单元格的表格数据

《Python实现获取带合并单元格的表格数据》由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,所以本文我们就来聊聊如何使用Python实现获取带合并单元格的表格数据吧... 由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,现将将封装成类,并通过调用list_exc

Nginx路由匹配规则及优先级详解

《Nginx路由匹配规则及优先级详解》Nginx作为一个高性能的Web服务器和反向代理服务器,广泛用于负载均衡、请求转发等场景,在配置Nginx时,路由匹配规则是非常重要的概念,本文将详细介绍Ngin... 目录引言一、 Nginx的路由匹配规则概述二、 Nginx的路由匹配规则类型2.1 精确匹配(=)2

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.