数据结构 | 利用二叉堆实现优先级队列

目录

一、二叉堆的操作

二、二叉堆的实现

2.1 结构属性

2.2 堆的有序性

2.3 堆操作


队列有一个重要的变体,叫作优先级队列。和队列一样,优先级队列从头部移除元素,不过元素的逻辑顺序是由优先级决定的。优先级最高的元素在最前,优先级最低的元素在最后。因此,当一个元素入队时,它可能直接被移到优先级队列的头部。

实现优先级队列的经典方法是使用叫作二叉堆的数据结构。二叉堆的入队操作和出队操作均可达到O(logn)

二叉堆有两个常见的变体:最小堆(最小的元素一直在队首)与最大堆(最大的元素一直在队首)。

本篇文章实现的是最小堆

一、二叉堆的操作

我们将实现以下基本的二叉堆方法。

  • BinaryHeap()新建一个空的二叉堆。
  • insert(k)往堆中加入一个新元素。
  • findMin()返回最小的元素,元素留在堆中。
  • delMin()返回最小的元素,并将该元素从堆中移除。
  • isEmpty()在堆为空时返回True,否则返回False。
  • size()返回堆中元素的个数。
  • buildHeap(list)根据一个列表创建堆。
>>> from pythonds.trees import BinaryHeap
>>> bh=BinaryHeap()
>>> bh.insert(5)
>>> bh.insert(7)
>>> bh.insert(3)
>>> bh.insert(11)
>>> print(bh.delMin())
3
>>> print(bh.delMin())
5
>>> print(bh.delMin())
7
>>> print(bh.delMin())
11

二、二叉堆的实现

2.1 结构属性

为了使二叉树能够高效地工作,我们利用树的对数性质来表示它。为了保证对数性能,必须维持树的平衡。平衡的二叉树是指,其根节点的左右子树含有数量大致相等的节点。在实现二叉堆时,我们通过创建一颗完全二叉树来维持树的平衡。在完全二叉树中,除了最底层,其他每一层的节点都是满的。在最底层,我们从左往右填充节点。

完全二叉树的另一个有趣之处在于,可以用一个列表来表示它,而不需要采用“列表之列表”或“节点与引用”表示法。由于树是完全的,因此,因此对于在列表中处于位置p的节点来说,它的左子节点正好处于位置2p;同理,右子节点处于位置2p+1。若要找到树中任意节点的父节点,只需使用python的整数除法即可。给定列表中位置n处的节点,其父节点的位置就是n/2。

2.2 堆的有序性

我们用来存储堆元素的方法依赖于堆的有序性。堆的有序性是指:对于堆中任意元素x及其父元素p,p都不大于x。

2.3 堆操作

新建二叉堆:

def __init__(self):self.heapList=[0]self.currentSize=0

接下来实现insert方法。将元素加入列表的最简单、最高效的方法就是将元素追加到列表的末尾。追加操作的优点在于,它能保证完全数的性质,但缺点是很可能会破坏堆的结构性质。不过可以写一个方法,通过比较新元素与其父元素来重新获得堆的结构性质。如果新元素小于其父元素,就将二者交换。

perUp方法:

def perUp(self,i):while i//2>0:if self.heapList[i]<self.heapList[i//2]:tmp=self.heapList[i//2]self.heapList[i//2]=self.heapList[i]self.heapList[i]=tmpi=i//2

向二叉堆中新加元素:

def insert(self,k):self.heapList.append(k)self.currentSize=self.currentSize+1self.perUp(self.currentSize)

正确定义insert方法后,就可以编写delMin方法。既然堆的结构性质要求根节点是树的最小元素,那么查找最小值就很简单。delMin方法的难点在于,如果在移除根节点之后重获堆的结构性质和有序性。可以分两步重建堆。第一步,取出列表中的最后一个元素,将其移到根节点的位置。移动最后一个元素保证了堆的结构性质,但可能破坏二叉堆的有序性。第二步,将新的根节点沿着树推到正确的位置,以重获堆的有序性。

perDown方法和minChild方法:

def percDown(self,i):while (i*2)<=self.currentSize:mc=self.minChild(i)if self.heapList[i]>self.heapList[mc]:tmp=self.heapList[i]self.heapList[i]=self.heapList[mc]self.heapList[mc]=tmpi=mcdef minChild(self,i):if i*2+1>self.currentSize:return i*2else:if self.heapList[i*2]<self.heapList[i*2+1]:return i*2else:return i*2+1

从二叉堆中删除最小的元素:

def delMin(self):retval=self.heapList[1]self.heapList[1]=self.heapList[self.currentSize]self.currentSize=self.currentSize-1self.heapList.pop()self.percDown(1)return retval

根据元素列表构建堆:

def bulidHeap(self,alist):i=len(alist)//2self.currentSize=len(alist)self.heapList=[0]+alist[:]while (i>0):self.percDown(i)i=i-1

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/79800.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

火爆全网,Python自动化测试Allure测试报告生成,最强总结...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 Allure测试报告框…

JavaWeb(9)——前端综合案例3(悬停显示下拉列表)

一、实例需求 ⌛ 实现类似百度首页的“一个简单的鼠标悬停显示的下拉列表效果”。 二、代码实现 ☕ <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><style>.dropdown-cont…

外部链接跳转到vue项目传递参数实现单点登录

1、问题背景描述&#xff1a; 我有一个困扰了很久项目需求&#xff0c;前台门户用的MVC&#xff0c;前台登录之后需要能点击某个按钮就能进入后台vue开发的前端项目&#xff0c;不需要重新登录。这个需求中mvc项目相对于vue项目来说是外部链接&#xff0c;他要跳转到vue项目&a…

9、Kubernetes核心技术 - Volume

目录 一、概述 二、卷的类型 三、emptyDir 四、hostPath 五、NFS 5.1、master服务器上搭建nfs服务器 5.2、各个slave节点上安装nfs客户端 5.3、创建Pod 六、PV和PVC 6.1、PV 6.1.1、PV资源清单文件示例 6.1.2、PV属性说明 6.1.3、PV的状态 6.2、PVC 6.2.1、PVC资…

git开发过程中的使用

1、先创建本地分支&#xff0c;然后修改代码 2、本地提交 push 3、合并为主分支 回到master分支

Bigemap如何添加谷歌地图?

工具 Bigemap gis office地图软件 BIGEMAP GIS Office-全能版 Bigemap APP_卫星地图APP_高清卫星地图APP 打开软件&#xff0c;要提示需要授权和添加地图&#xff0c;然后去点击选择地图这个按钮&#xff0c;列表中有个添加按钮点进去选择添加地图的方式。 第一种方式&#x…

UML—用例图的那些事

目录 背景: 1.用例图的发展史 过程: 1.用例图中的元素和关系 2.应用中的例子 总结&#xff1a; 背景: 1.用例图的发展史 用例图是一种常用的软件工程工具&#xff0c;用于描述系统的功能需求和用户与系统的交互。它在软件开发过程中起到了重要的作用&#xff0c;并且经历了…

【开源项目--稻草】Day06

【开源项目--稻草】Day06 1. 学生提问与解答功能2. 显示create.html2.1 HomeController中代码2.2 复用网页的标签导航条 3. 创建问题发布界面3.1 富文本编辑器 4.多选下列框5.动态加载所有标签和老师6. 发布问题的业务处理 1. 学生提问与解答功能 学生提问: 提问时指定标签和回…

VBA遍历Wrod所有表格每个单元格,单元格未尾两个回车替换

一、遍历 word中遍历所有表格的每个单元格。因为在单元格时会常出错。浪费了不少时间。 Sub a()Dim doc As Document, tb As Table, ce As cellDim rng As Range, p As ParagraphSet doc ActiveDocumentFor Each tb In doc.TablesFor Each ce In tb.Range.Cells 关键处就是这里…

Java中的Unsafe类详解

Java中的Unsafe类详解 1. Unsafe 概念2. Unsafe 构造及获取3. 功能和应用3.1 内存管理3.1.1 普通读写3.1.2 volatile 读写3.1.3 有序读写3.1.4 直接操作内存 3.2 CAS3.3 偏移量3.4 线程调度3.5 类加载3.6 内存屏障3.7 其他操作 4. 潜在风险和挑战5. 最佳实践5.1 使用案例&#…

QtAV for ubuntu16.04

下载ubuntu https://releases.ubuntu.com/16.04/ubuntu-16.04.7-desktop-amd64.iso 下载ffmpeg https://ffmpeg.org/download.html 下载QtAV https://github.com/wang-bin/QtAV/releases 更新 sudo apt update 安装库 sudo apt-get install libglu1-mesa-dev freeglut3-dev…

【算法系列 | 7】深入解析查找算法之—布隆过滤器

序言 心若有阳光&#xff0c;你便会看见这个世界有那么多美好值得期待和向往。 决定开一个算法专栏&#xff0c;希望能帮助大家很好的了解算法。主要深入解析每个算法&#xff0c;从概念到示例。 我们一起努力&#xff0c;成为更好的自己&#xff01; 今天第3讲&#xff0c;讲一…

【数据结构】链表(一)

链表&#xff08;一&#xff09; 文章目录 链表&#xff08;一&#xff09;01 引入02 概念及结构03 单向不带头不循环链表实现3.1 创建节点类型3.2 简易创建一个链表3.3 遍历链表每个节点3.4 获取链表长度3.5 查找是否包含关键字key是否在单链表当中3.6 头插法3.7 尾插法3.8 任…

MySQL 重置root 密码

5.7 版本 首先要把服务mysql57 关闭 net stop MySQL57 在安装的mysql57的程序的bin中 运行cmd&#xff08;管理员运行&#xff09; mysqld --defaults-file‘mysql存放数据的位置\my.ini’ --skip-grant-tables 上图 错误 注意&#xff1a;如果遇到mysqld: Can’t change dir…

【从零学习python 】02. 开发工具介绍

文章目录 编写Python代码一、常见的代码编辑工具二、运行Python程序三、Pycharm的下载和安装PyCharm的主要功能区域进阶案例 编写Python代码 根据我们之前介绍的知识&#xff0c;我们知道&#xff0c;所谓代码其实就是将一段普通文本按照一定的规范编写&#xff0c;然后交给电…

Cesium 加载ArcGIS Server切片服务错级问题

1.首先上官方api说明 ArcGisMapServerImageryProvider - Cesium Documentation 里面没有 zoomoffset参数!!! 2.如果按照互联网栅格切片规则 3857、4326、4490常用切片层级参数,则直接加载显示地图 viewer.imageryLayers.addImageryProvider(new Cesium.ArcGisMapServerI…

【Spring Boot】(三)深入理解 Spring Boot 日志

文章目录 前言一、日志文件的作用二、Spring Boot 中的日志2.1 查看输出的日志信息2.2 日志格式二、Spring Boot 中的日志2.1 查看输出的日志信息2.2 日志格式 三、自定义日志输出3.1 日志框架3.2 日志对象的获取3.3 使用日志对象打印日志 四、日志级别4.1 日志级别的作用4.2 日…

Oracle-expdp报错ORA-39077、06502(Bug-16928674)

问题: 用户在使用expdp进程导出时&#xff0c;出现队列报错ORA-39077、ORA-06502 ORA-31626: job does not exist ORA-31638: cannot attach to job SYS_EXPORT_SCHEMA_01 for user SYS ORA-06512: at "SYS.DBMS_SYS_ERROR", line 95 ORA-06512: at "SYS.KUPV$…

【修正-高斯拉普拉斯滤波器-用于平滑和去噪】基于修正高斯滤波拉普拉斯地震到达时间自动检测研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

解密HTTP代理爬虫中的IP代理选择与管理策略

在当今数据驱动的世界中&#xff0c;HTTP代理爬虫作为一项重要的数据采集工具&#xff0c;其成功与否往往取决于IP代理的选择与管理策略。作为一家专业的HTTP代理产品供应商&#xff0c;我们深知IP代理在数据采集中的重要性。在本文中&#xff0c;我们将分享一些关于HTTP代理爬…