快速办理的优先级队列与堆排序方法详解
优先队列
许多应用程序都需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。很多情况下是收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键值最大的元素。这种情况下,需要的数据结构支持两种操作:删除最大的元素和插入元素。这种数据结构类型叫优先队列。
这里,优先队列基于二叉堆数据结构实现,用数组保存元素并按照一定条件排序,以实现对数级别的删除和插入操作。
1.API
优先队列是一种抽象数据类型,它表示了一组值和对这些值的操作,抽象层使应用和实现隔离开来。
2.初级实现
1.无序数组实现
优先队列的 insert 方法和下压栈的 push 方法一样。删除最大元素时,遍历数组找出最大元素,和边界元素交换。
2.有序数组实现
插入元素时,将较大的元素向右移一格(和插入排序一样)。这样删除时,就可以直接 pop。
使用链接也是一样的逻辑。
这些实现总有一种操作需要线性级别的时间复杂度。使用二叉堆可以保证操作在对数级别的时间完成。
3.堆的定义
数据结构二叉堆可以很好地实现优先队列地基本操作。在二叉堆数组中,每个元素都要保证大于等于另两个特定位置地元素。同样,这两个位置地元素又至少要大于等于数组中另外两个元素,以此类推。用二叉树表示:
当一棵二叉树的每个结点都大于等于它的两个子节点时,它被成为堆有序。从任意结点向上,都能得到一列非递减的元素;从任意结点向下,都能得到一列非递增的元素。根结点是堆有序的二叉树中最大的结点。
二叉堆表示法
这里使用完全二叉树表示:将二叉树的结点按照层级顺序(从上到下,从左往右)放入数组中,不使用数组的第一个位置(为了方便计算),根结点在位置 1 ,它的子结点在位置 2 和 3,子结点的子结点分别在位置 4,5,6,7,一次类推。
在一个二叉堆中,位置 k 的结点的父节点位置在 k/2,而它的两个子结点在 2k 和 2k + 1。可以通过计算数组的索引而不是指针就可以在树中上下移动。
一棵大小为 N 的完全二叉树的高度为 lgN。
4.堆的算法
用长度为 N+1 的私有数组 pq[ ] 表示一个大小为 N 的堆。
堆在进行插入或删除操作时,会打破堆的状态,需要遍历堆并按照要求将堆的状态恢复。这个过程称为 堆的有序化。
堆的有序化分为两种情况:当某个结点的优先级上升(或在堆底加入一个新的元素)时,需要由下至上恢复堆的顺序;当某个结点的优先级下降(例如将根节点替换为一个较小的元素),需要由上至下恢复堆的顺序。
上浮(由下至上的堆的有序化)
当某个结点比它的父结点更大时,交换它和它的父节点,这个结点交换到它父节点的位置。但有可能比它现在的父节点大,需要继续上浮,直到遇到比它大的父节点。(这里不需要比较这个子结点和同级的另一个子结点,因为另一个子结点比它们的父结点小)
//上浮 private void Swim(int n) { while (n > 1 && Less(n / 2, n)) { Exch(n/2,n); n = n / 2; } }
下沉(由上至下的堆的有序化)
当某个结点 k 变得比它的两个子结点(2k 和 2k+1)更小时,可以通过将它和它的两个子结点较大者交换来恢复堆有序。交换后在子结点处可能继续打破堆有序,需要继续重复下沉,直到它的子结点都比它小或到达底部。
//下沉 private void Sink(int k) { while (2 * k <= N) { int j = 2 * k; //取最大的子节点 if (j < N && Less(j, j + 1)) j++; //如果父节点不小子节点,退出循环 if (!Less(k,j)) break; //否则交换,继续下沉 Exch(j,k); k = j; } }
知道了上浮和下沉的逻辑,就可以很好理解在二叉堆中插入和删除元素的逻辑。
插入元素:将新元素加到数组末尾,增加堆的大小并让这个新元素上浮到合适的位置。
删除最大元素:从数组顶端(即 pq[1])删除最大元素,并将数组最后一个元素放到顶端,减少数组大小并让这个元素下沉到合适位置。
public class MaxPriorityQueue { private IComparable[] pq; public int N; public MaxPriorityQueue(int maxN) { pq = new IComparable[maxN+1]; } public bool IsEmpty() { return N == 0; } public void Insert(IComparable value) { pq[++N] = value; Swim(N); } public IComparable DeleteMax() { IComparable max = pq[1]; Exch(1,N--); pq[N + 1] = null; Sink(1); return max; } //下沉 private void Sink(int k) { while (2 * k <= N) { int j = 2 * k; //取最大的子节点 if (j < N && Less(j, j + 1)) j++; //如果父节点不小子节点,退出循环 if (!Less(k,j)) break; //否则交换,继续下沉 Exch(j,k); k = j; } } //上浮 private void Swim(int n) { while (n > 1 && Less(n / 2, n)) { Exch(n/2,n); n = n / 2; } } private void Exch(int i, int j) { IComparable temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; } private bool Less(int i, int j) { return pq[i].CompareTo(pq[j]) < 0; } }
上述算法对优先队列的实现能够保证插入和删除最大元素这两个操作的用时和队列的大小成对数关系。这里省略了动态调整数组大小的代码,可以参考下压栈。
对于一个含有 N 个元素的基于堆的优先队列,插入元素操作只需要不超过(lgN + 1)次比较,因为 N 可能不是 2 的幂。删除最大元素的操作需要不超过 2lgN次比较(两个子结点的比较和父结点与较大子节点的比较)。
对于需要大量混杂插入和删除最大元素的操作,优先队列很适合。
改进
1. 多叉堆
基于数组表示的完全三叉树:对于数组 1 至 N 的 N 个元素,位置 k 的结点大于等于位于 3k-1, 3k ,3k +1 的结点,小于等于位于 (k+1)/ 3 的结点。
2.调整数组大小
使用动态数组,可以构造一个无需关注队列大小的优先队列。可以参考下压栈。
3.索引优先队列
在许多应用程序中,允许客户端引用优先级队列中已经存在的项目是有意义的。一种简单的方法是将唯一的整数索引与每个项目相关联。
堆排序
我们可以把任意优先队列变成一种排序方法:先将所有元素插入一个查找最小元素的优先队列,再重复调用删除操作删除最小元素来将它们按顺序删除。这种排序成为堆排序。
堆排序的第一步是堆的构造,第二步是下沉排序阶段。
1.堆的构造
简单的方法是利用前面优先队列插入元素的方法,从左到右遍历数组调用 Swim 方法(由上算法所需时间和 N logN 成正比)。一个更聪明高效的方法是,从右(中间位置)到左调用 Sink 方法,只需遍历一半数组,因为另一半是大小为 1 的堆。这种方法只需少于 2N 次比较和 少于 N 次交换。(堆的构造过程中处理的堆都比较小。例如,要构造一个 127 个元素的数组,需要处理 32 个大小为 3 的堆, 16 个大小为 7 的堆,8 个大小为 15 的堆, 4 个大小为 31 的堆, 2 个大小为 63 的堆和 1 个大小为127的堆,因此在最坏情况下,需要 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120 次交换,以及两倍的比较)。
2.下沉排序
堆排序的主要工作在第二阶段。将堆中最大元素和堆底元素交换,并下沉至 N--。相当于删除最大元素并将堆底元素放至堆顶(优先队列删除操作),将删除的最大元素放入空出的数组位置。
public class MaxPriorityQueueSort { public static void Sort(IComparable[] pq) { int n = pq.Length; for (var k = n / 2; k >= 1; k--) { Sink(pq, k, n); } //上浮需要遍历全部 //for (var k = n; k >= 1; k--) //{ // Swim(pq, k); //} while (n > 1) { Exch(pq,1,n--); Sink(pq,1,n); } } private static void Swim(IComparable[] pq, int n) { while (n > 1 && Less(pq,n / 2, n)) { Exch(pq,n / 2, n); n = n / 2; } } //下沉 private static void Sink(IComparable[] pq,int k, int N) { while (2 * k <= N) { int j = 2 * k; //取最大的子节点 if (j < N && Less(pq,j, j + 1)) j++; //如果父节点不小子节点,退出循环 if (!Less(pq, k,j)) break; //否则交换,继续下沉 Exch(pq, j,k); k = j; } } private static void Exch(IComparable[] pq, int i, int j) { IComparable temp = pq[i-1]; pq[i - 1] = pq[j - 1]; pq[j - 1] = temp; } private static bool Less(IComparable[] pq, int i, int j) { return pq[i - 1].CompareTo(pq[j - 1]) < 0; } public static void Show(IComparable[] a) { for (var i = 0; i < a.Length; i++) Console.WriteLine(a[i]); } }
堆排序的轨迹
将 N 个元素排序,堆排序只需少于 (2N lgN + 2N)次比较以及一半次数的交换。2N 来自堆的构造,2N lgN 是每次下沉操作最多需要 2lgN 次比较。
先下沉后上浮
在排序过程中,大多数重新插入堆中的项目都会一直到达底部。因此,通过避免检查元素是否已到达其位置,可以简单地提升两个子结点中的较大者直到到达底部,然后上浮到适当位置,从而节省时间。这个方法将比较数减少了2倍,但需要额外的簿空间。只有当比较操作代价较高时可以使用这种方法。(例如将字符串或其他键值较长类型的元素排序)。
堆排序是能够同时最优利用空间和时间的方法,在最坏情况下也能保证 ~2N lgN 次比较和恒定的额外空间。当空间紧张时,可以使用堆排序。但堆排序无法利用缓存。因为它的数组元素很少喝相邻的其他元素比较,因此缓存未命中的次数要远高于大多数比较都在相邻元素之间进行的算法。
推荐阅读
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
快速办理的优先级队列与堆排序方法详解
-
简单易懂!排序方法详解:优先队列的工作机制与实战实现
-
TypeScript里的数据结构与算法(16):详解优先级队列PriorityQueue
-
堆与优先级队列详解:从数据结构的角度看赫夫曼树与优先处理队列的对比
-
LeetCode 973题:寻找离原点最近的K个点 (排序、优先队列与快速排序方法)
-
详解优先队列的工作机制与使用方法
-
理解Java核心:堆排序与优先级队列的基础讲解
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)
-
快速了解:PriorityQueue - 优先级队列(堆)的实际操作与应用