优先队列(PriorityQueue)
在数据结构中，普通的队列是先进先出，但有时我们可能并不想有这么固定的规矩，我们希望能有一个带优先级的队列。考虑在现实生活中，一些服务排队窗口会写着“军人依法优先”；送进医院的患者，即便是按顺序到达的，生病更加严重的往往优先级也会更高；还有操作系统中的作业调度也和优先级有关......
于是我们能不能改进队列？使得队列是有一定优先级的，这样能让一些事物和任务的处理变的更加灵活。当然是可以的，最基本的我们可以基于线性结构来实现，考虑基于线性结构的时间复杂度：
1、队列是一种FIFO（First-In-First-Out）先进先出的数据结构，对应于生活中的排队的场景，排在前面的人总是先通过，依次进行。
2、优先队列是特殊的队列，从“优先”一词，可看出有“插队现象”。比如在火车站排队进站时，就会有些比较急的人来插队，他们就在前面先通过验票。优先队列至少含有两种操作的数据结构：insert（插入），即将元素插入到优先队列中（入队）；以及deleteMin（删除最小者），它的作用是找出、删除优先队列中的最小的元素（出队）。
结构操作 入队 出队
普通线性结构 O(1) O(n)
顺序线性结构 O(n) O(1)
普通线性结构实现的优先队列出队时间复杂度是O(n)，因为出队要拿出***先的元素，也就是相对***的元素（注意：大小是相对的，我们可以指定比较规则），从而要扫描一遍整个数组选出***的取出才行。而对于顺序线性结构的入队操作，入队后可能破坏了原来的有序性，从而要调整当前顺序。
可以看到使用线性结构总有时间复杂度是O(n)的操作，还有没有更好的实现方式呢，当然是有的，这就要来聊一聊堆Heap。
堆严格意义上来说又叫二叉堆（Binary Heap），因为它的结构是一颗完全二叉树，堆一般分为***堆和最小堆。
堆性质：
结构性：堆是一颗除底层外被完全填满的二叉树，底层的节点从左到右填入，这样的树叫做完全二叉树。即缺失结点的部分一定再树的右下侧。
堆序性：由于我们想很快找出最小元，则最小元应该在根上，任意节点都小于它的后裔，这就是小顶堆（Min-Heap）；如果是查找***元，则***元应该在根上，任意节点都要大于它的后裔，这就是大顶堆(Max-heap)。
***堆：父亲节点的值大于孩子节点的值
最小堆：父亲节点的值小于孩子节点的值
由于是完全二叉树，节点的索引之间有着一定的关系，故我们可以使用数组来存储二叉堆，具体如下：
如果从索引为0开始存储，则父亲和孩子节点的索引关系如下：
当我们需要向一个***堆添加一条新的数据时，此时我们的堆变成了这样。
此时，由于新数据的加入已经不符合***堆的定义了。所以我们需要对新加入的数据进行shift up操作，将它放到它应该在的位置。shift up操作时我们将新加入的数据与它的父节点进行比较。如果比它的父节点大，则交换二者。
此时我们就完成了 对新加入元素的shift up操作。
当我们从堆中(也就是优先队列中)取出一个元素时。我们是将堆顶的元素弹出。(只能从堆顶取出)
此时这个堆没有顶了，那么该怎么办呢？我们只需要把这个堆最后一个元素放到堆顶就可以了。
此时我们就完成了弹出一个元素之后的shift down操作。
replace:去除***元素后，放入一个新元素
实现：可以先extractMax,再add，两次longn操作。
实现:将堆顶的元素替换以后sift down，一次O(logn)操作
将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn),heapify的过程，算法的复杂度为O(n).
heapify:将任意数组整理成堆的形状。
首先将一个数组抽象成一个堆。这个过程，我们称之为heapify。
之后我们找到这个堆中***个非叶子节点，这个节点的位置始终是数组的数量除以2，也就是索引5位置的27，从这个节点开始，对每一个非叶子的节点,，进行shift down操作。
27比它的子节点51要小，所以交换二者。
接下来我们看索引2位置的20。首先呢，我们需要将20与它两个子节点中较大的51交换。
每个节点堆化的时间复杂度是O(logn)，那 个节点的堆化的总时间复杂度是O(nlogn)。
推导过程
堆化节点从倒数第二层开始。堆化过程中，需要比较和交换的节点个数与这个节点的高度k成正比。
所以 heapify() 时间复杂度是 O(n).
建堆后，数组中的数据是大顶堆。把堆顶元素，即***元素，跟最后一个元素交换，那***元素就放到了下标为n的位置。
这个过程有点类似上面的“删除堆顶元素”的操作，当堆顶元素移除之后，把下标n的元素放堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆。一直重复这个过程，直到最后堆中只剩下下标为1的元素，排序就完成了。
topk和selectk问题既可以使用快排思想解决，也可以使用优先队列解决。
快排:O(n) 空间O(1)
优先队列:O(nlogk) 空间O(k)
优先队列的有i是，不需要一次性知道所有数据,数据流的方式处理。
什么是优先队列？
优先队列(priority queue)普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有***优先级的元素***删除。优先队列具有***进先出 （largest-in，first-out）的行为特征。
堆（Heap）和有优先队列(Priority Queue)
1 优先队列（Priority Queue）
优先队列与普通队列的区别：普通队列遵循先进先出的原则；优先队列的出队顺序与入队顺序无关，与优先级相关。
优先队列可以使用队列的接口，只是在实现接口时，与普通队列有两处区别，一处在于优先队列出队的元素应该是优先级***的元素，另一处在于队首元素也是优先级***的元素。
优先队列也可以使用不同的底层实现，不同底层实现的时间复杂度如下：
从上图可以看出，使用"堆"这种数据结构来实现优先队列是比较高效的。
2 二叉堆（Binary Heap）
二叉堆就是一棵满足特殊性质的二叉树
首先，二叉堆是一棵完全二叉树，"完全二叉树"，不一定是满二叉树，不满的部分一定位于整棵树的右下侧。
其次，堆中某个节点的值总是不大于其父节点的值（***堆）；相应的，堆中的某个节点的值总是不小于其父节点的值（最小堆）。
节点值的大小与其所处的层次没有必然联系，即，***堆中，只需保证每个节点不大于其父节点即可，至于大不大于其父节点的兄弟节点，没有任何关系。
可以用数组来存储二叉堆，如下图所示：
用动态数组实现二叉堆的业务逻辑如下：
测试用动态数组实现的二叉堆
二叉堆的时间复杂度分析
由于堆是一棵完全二叉树，所以堆不会退化成链表。
3.用***堆实现一个优先队列（Priority Queue）
实现优先队列的业务逻辑如下：
4.优先队列的应用：从N个元素中，选出前M个
解决方案：使用优先队列，维护当前的M个元素，然后不断更新元素，直到扫描完所有N个元素。
需要使用"最小堆"来进行底层的实现，因为最终获取的是前M个元素，通过最小堆的extractMin方法，可以不断的剔除堆中的最小元素
也可以使用***堆来实现，我们只要规定元素越小，优先级越高。
使用最小堆实现的业务逻辑如下：
优先队列
我们知道普通队列的特点是先进先出，但是优先队列的特点则遵守以下两条规则：
- ***优先队列：无论入队的顺序，当前***的元素先出列。
- 最小优先队列：无论入队的顺序，当前最小的元素先出列。
说明：在学习优先队列前必须先理解 二叉堆
这时候就是 二叉堆 发挥作用的时候了。我们知道二叉堆有以下特性：
- ***堆：堆顶是整个数组中***的元素，且任何父节点的值都大于其子节点
- 最小堆：堆顶是整个数组中最小的元素，且任何父节点的值都小于其子节点
对于优先队列，介绍以下几种操作：
入队操作；
出队操作；
说明：以最小优先队列为例
1.入队操作
优先队列本质上就是用二叉堆来实现的，每次插入一个数据都是插入到数据数组的最后一个位置，然后再做上浮操作，如果插入的数是数组中***数，自然会上浮到堆顶。如“图1 入队操作”所示：
2.出队操作
出队操作就是返回堆顶最小堆的数据之后用数组最后的数插入到堆顶，之后再做下沉操作。如“图2 出队操作”所示：
因为二叉堆上浮和下沉的时间复杂度都为log2(n)，所以入队和出队的时间复杂度也是log2(n)。
优先队列是基于二叉堆实现的，优先指的是按某种优先级优先出列而不是先入先出。操作系统的阻塞机制正是有优先队列实现。
【数据结构】堆（优先队列）：二叉堆、d堆、左式堆、斜堆与二项队列
这是数据结构类重新复习笔记的第 五 篇，同专题的其他文章可以移步：
堆 （Heap）又称为 优先队列 （priority queue），在队列的基础上，堆允许所有队列中的元素不一定按照 先进先出 （FIFO）的规则进行，而是使得每个元素有一定的优先级，优先级高的先出队列。
优先队列至少存在两个重要的操作：
有几种简单而明显的方法实现优先队列。
二叉堆 （binary heap）是一种对于优先队列的实现，可以简称为堆
堆是一棵 完全二叉树 （complete binary tree），即所有节点都必须有左右两个子节点，除了最后一排元素从左向右填入，直到没有元素为止。
很显然，一棵高为h的完全二叉树有 2^h 到 2^(h+1)-1 个节点，即其高度为 logN 向下取整。
完全二叉树的好处在于其规律性，可以使用一个数组而不需要链表来表示
对于数组中任一位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 (2i+1) 上，它的父亲则在位置 i/2 向下取整上。
因此，不仅不需要链，而且遍历该树所需要的操作也极简单，在大部分计算机上都可能运行得非常快。唯一问题是***的堆的大小需要事先估计。
使操作可以快速执行的性质是 堆序性质 （heap-order property）：对于每一个节点X，X的父节点中的键小于等于X中的键，除没有父节点根节点外。
将待插入的元素首先放置在最后一个位置上，以保证他是一个完全二叉树，然后将该元素与其父节点（i/2向下取整）比较，如果比其父节点小，就将两者互换，互换后再和新的父节点比较，这种方式称为 上滤 （percolate up），得到一个小顶堆（min heap），如果比较的时候是较大的值向上走，就会得到一个大顶堆（max heap）
比如向一个小顶堆中插入元素14的操作：
找出、返回并删除最小元非常简单，最小元就是根节点处的元素，将其返回并删除。接下来是处理这个B。首先拿下最后一个元素X，如果元素X比B的两个子节点都小，可以直接将X插入到B的位置，如果X比B的两个子节点中的任意一个大，就不能插入，此时找到两个子节点中较小的那个放到B处，B转而移至这个子结点处。重复如上的步骤直到X可以插入B处为止。这个操作成为 下滤 （percolate down）
比如从一个小顶堆中删除根节点
decreaseKey(p, A) 操作减小在位置p处的元素的值，减少量为A，可以理解为调高了某个元素的优先级。操作破坏了堆的性质，从而需要上滤操作进行堆的调整。
increaseKey(p, A) 操作增加在位置p处的元素的值，增加量为A，可以理解为降低了某个元素的优先级。操作破坏了堆的性质，从而需要下滤操作进行堆的调整。
remove(p) 操作删除在堆中位置p处的节点，这种操作可以通过连续执行 decreaseKey(p, ∞) 和 deleteMin() 完成，可以理解马上删除某个一般优先级的元素
即将一个原始集合构建成二叉堆，这个构造过程即进行N次连续的 insert 操作完成
定理 ：包含 2^(h+1)-1 个节点且高度为h的理想二叉树（perfect binary tree）的节点的高度和为 2^(h+1)-1-(h+1)
d堆 （d-Heaps）是二叉堆的简单推广，它与二叉堆很像，但是每个节点都有d个子节点，所以二叉堆是d为2的d堆。d堆是完全d叉树。比如下边的一个3堆。
d堆比二叉堆浅很多，其insert的运行时间改进到 O(logdN) 。但是deleteMin操作比较费时，因为要在d个子节点中找到最小的一个，需要进行d-1次比较。d堆无法进行find操作，而且将两个堆合二为一是很困难的事情，这个附加操作为merge合并。
注意！ 在寻找节点的父节点、子节点的时候，乘法和除法都有因子d。如果d是一个2的幂，则可以通过使用二进制的 移位 操作计算，这在计算机中是非常省时间的。但是如果d不是一个2的幂，则使用一般的乘除法计算，时间开销会急剧增加。有证据显示，实践中，堆可以胜过二叉堆
这些高级的数据结构很难使用一个数据结构来实现，所以一般都要用到链式数据结构，这种结构可能会使得其操作变慢。
零路径长 （null path length）npl(X)：定义为从一个X节点到其不具有两个子节点的子节点的最短路径长，即具有0个或者1个子节点的节点npl=0，npl(null)=-1，任意节点的零路径长都比其各个子节点中零路径长最小值多1。
左式堆 （leftist heap）是指对于任意一个节点X，其左子节点的零路径长都大于等于其右子节点的零路径长。很显然，左式堆趋向于加深左路径。比如下边的两个堆，只有左边的是左式堆，堆的节点标示的是该节点的零路径长。
左式堆的实现中，需要有四个值：数据、左指针、右指针和零路径长。
定理 ：在右路径上有r个节点的左式堆必然至少有 2^r-1 个节点
merge 是左式堆的基本操作， insert 插入可以看成是一个单节点的堆与一个大堆的 merge ， deleteMin 删除最小值操作可以看成是首先返回、删除根节点，然后将根节点的左右子树进行 merge 。所以 merge 是左式堆的基本操作。
假设现在有两个非空的左式堆H1和H2，merge操作递归地进行如下的步骤：
例如如下的两个堆：
将H2与H1的右子树（8--17--26）进行merge操作，此时（8--17--26）和H2的merge操作中又需要（8--17--26）和H2的右子堆（7--37--18）进行merge操作……如此递归得到如下的堆：
然后根据递归的最外层（回到H1和H2的merge的第二步），将上边合并的堆成为H1的右子堆
此时根节点（3）处出现了左右子堆不符合左式堆的情况，互换左右子堆并更新零路径长的值
斜堆 （skew heap）是左式堆的自调节形式，实现起来极其简单。斜堆和左式堆的关系类似于伸展树和AVL树之间的关系。斜堆是具有堆序的二叉树，但是不存在对树的结构的现限制。不同于左式堆，关于任意结点的零路径长的任何信息都不保留。斜堆的右路径在任何时刻都可以任意长，因此，所有操作的最坏情形运行时间均为O(N)。然而，正如伸展树一样，可以证明对任意M次连续操作，总的最坏情形运行时间是 O(MlogN)。因此，斜堆每次操作的 摊还开销 （amortized cost）为O(logN)
斜堆的基本操作也是merge合并，和左式堆的合并相同，但是不需要对不满足左右子堆的左式堆条件的节点进行左右子堆的交换。斜堆的交换是无条件的，除右路径上所有节点的***者不交换它的左右儿子外，都要进行这种交换。
比如将上述的H1和H2进行merge合并操作
首先进行***步，除了交换左右子树的操作与左式堆不同，其他的操作都相同
将合并的堆作为H1的右子堆并交换左右子堆，得到合并后的斜堆
二项队列 （binomial queue）支持merge、insert和deleteMin三种操作，并且每次操作的最坏情形运行时间为O(logN)，插入操作平均花费常数时间。
二项队列不是一棵堆序的树，而是堆序的树的集合，成为 森林 （forest）。堆序树中的每一棵都是有约束的 二项树 （binomial tree）。二项树是每一个高度上至多存在一棵二项树。高度为0的二项树是一棵单节点树，高度为k的二项树Bk通过将一棵二项树Bk-1附接到另一棵二项树Bk-1的根上而构成的。如下图的二项树B0、B1、B2、B3和B4。
可以看到二项树Bk由一个带有儿子B0，B1，……，Bk-1的根组成。高度为k的二项树恰好有2^k个节点，而在深度d处的节点数为二项系数Cdk。
我们可以使用二项树的集合唯一地表示任意大小的优先队列。以大小为13的队列为例，13的二进制表示为1101，从而我们可以使用二项树森林B3、B2、B0表示，即二进制表示的数中，第k位为1表示Bk树出现，第k位为0表示Bk树不出现。比如上述的堆H1和堆H2可以表示为如下的两个二项队列：
二项队列额merge合并操作非常简单，以上边的二项队列H1、H2为例。需要将其合并成一个大小为13的队列，即B3、B2、B0。
首先H2中有一个B0，H1中没有，所以H2中的B0可以直接作为新的队列的B0的树
其次H1和H2中两个B1的树可以合并成一个新的B2的树，只需要将其中根节点较小的堆挂到根节点较大的堆的根节点上。这样就得到了三棵B2堆，将其中根节点***的堆直接放到新队列中成为它的B2堆。
最后将两个B2堆合并成一个新队列中的B3堆。
二项队列的deleteMin很简单，只需要比较队列中所有二项堆的根节点，返回和删除最小的值即可，时间复杂度为O(logN)，然后进行一次merge操作，也可以使用一个单独的空间每次记录最小值，这样就可以以O(1)的时间返回。
森林中树的实现采用“左子右兄弟”的表示方法，然后二项队列可以使用一个数组来记录森林中每个树的根节点。
例如上边的合成的二项队列可以表示成如下的样子：
STL中，二叉堆是通过 priority_queue 模板类实现的，在头文件 queue 中，STL实现一个大顶堆而不是小顶堆，其关键的成员函数如下：
priority_queue
priority_queue又称为优先队列，其底层是用 堆 来进行实现的。在优先队列中，队首元素一定是当前队列中优先级***的那一个。
当然，可以在任何时候往优先队列里面加入（push）元素，而优先队列底层的数据结构堆（heap）会随时调整结构，使得 每次的队首元素都是优先级***的。
定义：priority_queuetypename name;
和队列不一样的是，优先队列没有front（）和back（）函数，而 只能通过top（）函数来访问队首元素。
（1）push（）
（2）top（）： 可以获得队首元素（即堆顶元素）
（3）pop（）： 队首元素（即堆顶元素）出队
（4）empty（）：和queue一样
（5）size（）：
priority_queue优先级的设置：
下面介绍基本数据类型和结构体类型的优先级设置方法
①基本数据类型的优先级设置
priority_queueint, vectorint, lessint q; //lessint表示数字大的优先级越大，而greaterint表示数字小的优先级越大
priority_queue int , vector int , greaterint q; //vectorint是用来承载底层数据结构堆（heap）的容器
②结构体的优先级设置
完整示例：
此处小于号的重载于排序函数sort中的cmp函数有些类似。事实上，两者的作用确实是类似的， 只不过效果看上去似乎是“相反”的。 在排序中，如果是“return f1.price f2.price”，那么则是按价格从高到低排序，但是在优先队列中却是把价格低的放到队首。原因在于，优先队列本身默认的规则就是优先级高的放在队首，因此把小于号重载为大于号的功能时只是把这个规则反向了一下。如果读者无法理解，那么不妨记住， 优先队列的这个函数与sort中的cmp函数的效果是相反的。
有没有办法跟sort中的cmp函数那样写在结构体外面呢？
自然是有办法的，只需把friend去掉，把小于号改成一对小括号，再把重载的函数写在结构体外面，同时将其用struct包装起来。
关于优先队列和优先队列是最小堆还是最大堆呢的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。