【c++深入系列】：万字详解priority_queue（附模拟实现的源码）

🔥 本文专栏：c++
🌸作者主页：努力努力再努力wz

在这里插入图片描述

💪 今日博客励志语录： 真正的强大，不是从不跌倒，而是每次跌倒后都能笑着站起来

★★★ 本文前置知识：

模版

引入

那么priority_queue便是我们c++的stl库中的又一个容器，那么它便是我们是熟知的优先级队列，那么我们就可以从该容器的名字看出它的特点，那么它在队列的基础上加了一个优先级来修饰，我们知道队列是一个先进先出的数据结构，那么所谓的优先级则决定了哪些在队列中的元素谁能够在队列的前方，意味着该元素的优先级高，那么它就会率先弹出该队列，而优先级低的，则只能在队列的尾部，那么它就不会被率先被弹出队列，那么这个优先级则是可以由我们用户自己定义。

那么知道了优先级队列的一个概念之后，那么接下来读者关心的第一个问题，肯定就是优先级队列底层结构是什么，也就是采取的是什么方式来实现优先级队列的呢？那么估计有一部分读者想当然的就认为优先级队列采取就是用队列来实现，那么根据自己前面学习栈和队列容器的经验，那么这里优先级队列的实现可以采取容器适配器模式，里面定义一个队列，然后复用队列的成员函数即可了，但是事实上，c++的stl的设计者底层并没有采取队列来实现，而是采取的是堆这个结构，那么人家采取堆而不是队列肯定有自己的原因，那么这个原因是什么我会在后文提到，那么在知道这个原因之前，那么首先我们就得知道什么是堆结构，所以本文的第一部分内容，便是回顾与讲解堆，那么我相信有的读者对这个结构是十分熟悉，如果熟悉的话，那么就可以跳过这部分内容，如果不熟悉感到有些陌生的读者，那么可以看看这部分内容，帮组你回忆一下堆结构，而优先级队列的实现关键就是堆

堆

什么是堆

那么堆这个名字一听，很多初学者会以为它是继顺序表和链表以及栈和树等等数据结构之后又一个新的数据结构，但其实堆本质就是一棵二叉树，那么为什么把这棵二叉树给称之为堆呢，那么是因为这棵二叉树不仅能够存储数据，而且其最大的作用是可以对树中的所有的节点进行排序，所以这个堆就是一棵特殊的二叉树，那么要能做到排序，那么堆就必须满足一个性质，那么就是根节点必须大于或者等于它的左右孩子节点，并且递归的对于左右子树来说，也得同样满足其根节点大于或者等于其孩子节点，那么我们发现如果该二叉树满足该性质之后，此时对于该整个二叉树的根节点来说，其便有了意义，那么该二叉树的根节点是该二叉树中所有节点中元素最大的一个节点，那么该根节点也被称之为堆顶，那么说到这里，那么想必读者就能知道堆排序的原理了，由于堆顶是整个元素最大的，那么接下来我要做的就是删除堆顶元素，然后对除了堆顶的剩余的所有元素再来建堆，那么此时由剩余节点再来组成一棵满足堆性质的完整的二叉树，那么该二叉树中根节点是最大的，那么此时我们就只需获取根节点的元素值从而找到次大的元素，那么该二叉树也称之为大根堆，因为堆顶是整个堆中所有元素最大的，那么既然有大根堆，那么肯定就要小根堆，那么小根堆就是满足根节点小于或者等于其左右孩子，并且递归的左右子树都得满足该性质，那么此时对于小根堆来说，那么其堆顶就是该堆最小的元素

那么知道了堆排序大致的原理之后，那么有的读者可能此时纠结于某个具体的操作等细节，比如怎么删除堆顶以及删除完之后这个建堆又怎么实现，那么先别急着关注这些，那么我们先循序渐进，那么通过上文的讲述，你知道了堆的概念也就是什么是堆，那么它是一棵满足特殊性质的二叉树，那么接下来的关注点就是如何实现构建这棵二叉树，那么我们知道二叉树有两种方式实现，第一种就是定义一个二叉树的节点，那么每一个节点分别有两个指针域，指向其对应的左右孩子，还有一个数据域来存储数据，那么第二种方式就是通过数组来实现，那么这两种方式都能够实现构造一棵二叉树，但是具体选择哪一个，那么我们得讲解建堆操作之后，那么读者自然才能明白体会到选择哪个实现方式更合理和优秀，这里就先埋一个伏笔。

建堆

那么使用堆的需求肯定就是我们要对一个区间的数据进行排序，那么我们第一步要做的就是将这个区间中的数据给构造成一个满足堆性质的二叉树，那么此时就需要我们进行建堆操作，那么建堆的方式有两种，那么分别是向上调整建堆和向下调整建堆，那么首先我先来讲解一下向上调整建堆

1.向上调整建堆

原理

那么向上调整建堆的核心思想就是从上往下依次构建出满足堆性质的二叉树，那么所谓的从上往下就是从根节点开始依次往下构建二叉树，那么此时我们可以理解为我们的满足堆性质的二叉树的初始状态是一棵空树，也就是没有任何节点，那么此时我们再将要排序区间里面的数据依次插入到该树中，那么每一次新插入的位置都是从当前这棵二叉树的最后一层的最后一个叶子节点位置的右侧第一个叶子节点处（如果该最后一个叶子节点是该层的最右侧节点，那么新插入的位置则是下一层第一个），因为我们是从上往下从左往右依次添加节点，那么每次新插入的位置就是该二叉树最后一个叶子节的右侧，所以按照这种插入方式，那么堆的本质就是一棵完全二叉树，那么我们将数据成功插入到该二叉树中还并没有结束，因为我们该二叉树要满足堆性质，也就是根节点要大于或者等于左右孩子节点，那么此时你虽然你添加了一个叶子节点，但是添加玩之后不能破坏二叉树的堆性质，比如你这个新添加的叶子节点可能会大于根节点（以大根堆为例），那么此时你插入完之后的下一步就是调整新插入的节点的位置，那么如果它大于根节点，就与根节点的值进行交换，然后依次与沿途的祖先节点比较，直到不大于根节点结束，这就是所谓的向上调整

那么肯定会有读者会思考向上调整这种方式为什么是正确？

那么由于我们每次在插入节点之前，那么该二叉树是满足堆性质，也就是根节点大于等于左右孩子节点，那么我们知道此时新插入的节点的父节点一定是大于等于它的兄弟节点（如果新插入的节点是右孩子），那么如果它大于父节点，那么意味着它一定大于它的兄弟节点，所以新插入的节点与根节点交换之后的结果是满足堆性质，即交换之后满足根节点大于或者等于左右孩子节点，那么它同理可以重复同样的方式与沿途的祖先节点比较，那么沿途被换下来的祖先节点也一定是大于等于它左右子树中的所有节点的，所以能保证该沿途下的节点都满足堆性质，并且新插入的节点只和沿途节点比较，那么其他分支的节点不会受到影响，而我们说过在插入节点之前，那么二叉树已经满足堆性质，所以调整结束后，整个二叉树就满足堆性质

所以根据我们上文的分析，我们就知道能够向上调整的前提一定是你节点插入之前，该二叉树一定是满足堆性质的，如果该二叉树不满足堆性质，那么你的调整是没有意义的，你与根节点比较，那么根节点都可能小于的的兄弟节点，你与其交换也没有任何用

那么这里我们就可以解决上文没谈到埋的那个伏笔了，也就是选择哪种方式构建二叉树，是链表还是数组，那么这里我们根据采取向上调整建堆的原理，我们就可以知道，那么每次对新插入的节点向上调整的过程，都需要与沿途的父节点进行比较，那么如果你采取的是链表的方式，此时你的每一个节点光有两个指向左右孩子节点的指针还不够，还得添加一个指向父节点的指针，其次我们上文也说到，每次插入的节点都是该二叉树的最后一个叶子节点的右侧因为我们是从上往下从左往右依次插入，那么此时你还得每次都遍历一遍二叉树获取到当前最后一个叶子节点然后插入再去调整，那么这就是采取链表实现向上调整的建堆方式，那么刚才的这种方式绝对没错，肯定能够实现，但是缺陷也太明显了，那就是太复杂并且效率太低

那么第二种方式是数组，那么首先我们是如何通过这个数组这个连续的物理结果映射到二叉树这个逻辑结构上呢，那么就是通过数组的下标，那么我们为该二叉树中的每一个节点编号，从根节点开始从上往下从左往右依次给编号为1开始往后，那么根节点和左右孩子节点的索引就满足一个公式：

假设根节点编号为i
$左孩子节点索引 = 2 i + 1$

$右孩子节点索引 = 2 i + 2$

假设已知左孩子索引为k1,右孩子索引为k2：
$父节点索引 = (k 1 - 1) / 2$

$父节点索引 = (k 2 - 1) / 2$

那么这个公式的证明你可以自己观察枚举来证明，通俗点来说，就是自己画一个二叉树自己随便算一下，发现根节点与左右孩子一定是满足该公式，严格一点，你可以通过数学归纳法来证明，这里我就不再讲述该证明方式了
在这里插入图片描述
所以根据这个公式，那么数组的下标就能够描述二叉树的父子节点关系从而建立逻辑映射，而堆本质是一棵完全二叉树，那么堆中的节点在数组中是连续存放的，那么数组的空间利用率就很高，而根据上文的向上调整建堆的原理，而数组由于可以通过下标随机访问的特性，那么我们就可以通过子节点的编号来计算父节点，然后比较，更为关键的是，每次新插入的节点就是该数组的有效数据的末尾，因为从左往右依次插入，那么我们只需维护一个变量size就能得到数组有效数据的末尾的下标，无序遍历，所以采取数组实现是更为合理和高效
在这里插入图片描述

实现

那么关于向上调整的实现，有的小伙伴想用递归因为该二叉树结构，其实这里直接用循环即可，不用递归，那么循环的终止条件就是如果此时你的新插入的节点都被调到根节点（堆顶）了，那么根节点上面都没有节点了也就是新插入的节点的下标等于0，你就没必要调了直接退出循环，或者说你向上调整的过程中，此时被调整的该节点你小于等于了根节点（以大根堆为例），那么意味着此时整个二叉树都满足堆性质，那么也没有必要调直接退出循环，那么如果大于的话，那么此时就交换根节点与该节点的值，然后该节点此时就作为根节点，然后进入下一次循环与每次按照公式计算出它的父亲节点然后比较比较

void adjustUp(vector<datatype>& l1，size_t child)//这是大堆的向上调整，小堆的话就改下比较逻辑即可
{size_t parent = (child - 1) / 2;while (child > 0){if (l1[child] > l1[parent]){std::swap(l1[child], l1[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.向下调整建堆

原理

那么向上调整建堆，就是从顶到底依次构建我们的满足堆性质的二叉树，那么向下调整顾名思义就是从底到顶构建我们的二叉树，那么还是一样，我们还是有一个要排序区间的数据，那么我们先把他们放到一个数组当中，意味着这些数据整体构成了一棵二叉树，但是此时这棵二叉树是不满足堆性质的，必定需要经过调整

向上调整建堆的前提就是插入节点之前，该二叉树已经满足堆性质，而对于向下调整，那么其也要满足一个前提，那么就是被调整的位置肯定是二叉树中的某个节点，那么该前提就是该节点的左右子树必须得满足堆性质，才可以对该位置向下调整建堆，因为向下调整建堆的原理，就是该节点与其左右孩子节点中较大的比较，如果它小于较大的孩子节点（以大堆为例），那么就与该孩子节点的较大值交换，然后依次沿途往下比较，直到调整到正确位置，如果左右子树不满足堆性质，那么意味着至少有一个子树不满足堆性质，那么假设你交换到其中一个子树中去，而另一个子树已经不满足堆性质，那么你交换也没用，所以必须满足该前提

那么为什么向下调整建堆这种交换式正确的呢？

那么由于我们得到较大孩子，如果较大孩子比该根节点大，那么我们可以放心交换，那么交换后，新的根节点一定大于左右孩子，那么一定是满足堆性质，所以这种交换是正确的

其次就是为什么我们从倒数第二次开始调整，就是因为向下调整的前提条件要求其左右子树满足堆性质，而倒数第一层的左右子树都为空，那么左右子树都为空可以理解为左右子树都是无穷小，那么倒数第一层天然满足堆性质，那么我们直接从倒数第二层开始调整，那么到时第二层都满足对性质之后，那么我们就可以调整倒数第三层依次往上，最终构建一个整体的堆

实现

那么这里现在我们持有一个数组下标，对应某个需要向下调整的节点，那么它的左右子树已经满足堆性质，那么接下来我们就先得到较大孩子，然后比较该节点与较大孩子的大小，然后如果其小于较大孩子，那么就交换，此时的节点的位置就到了给较大孩子的位置，然后进入下一次循环，每次循环会计算出左孩子和右孩子节点，然后得到较大孩子，然后比较，一旦调整到最底部或者根节点大于等于较大孩子节点，就不需要调整，直接退出循环

void adjustDown(vetcor<datatype>& l1,size_t parent)//这里是大根堆的向下调整，小根堆的向下调整只需修改比较逻辑即可
{size_t child = parent * 2 + 1;while (child < l1.size()){int fit_child = child;if (child + 1 < l1.size() &&l1[child+1]>l1[child])){fit_child= child + 1;}if (l1[fit_child]>l1[parent]){std::swap(_con[parent], _con[fit_child]);parent = fit_child;child = 2 * parent + 1;}else{break;}}
}

3.两种建堆方式的效率比较

那么这里我们既可以才起向上调整建堆，那么也可以采取向下调整建堆，那么这两种方式究竟谁效率更高了，那么就需要我们来比较一下这两种方式的一个时间复杂度，那么我们就得估算一下这两种方式的时间复杂度，那么我们就以最坏时间复杂度来衡量，那么假设这里我们有高度为h层的满二叉树，那么我们先来估计向下调整建堆的时间复杂度：

那么向下调整建堆是从倒数第二层开始调整，那么由于是估计最坏的时间复杂度，那么从倒数第二层往上，那么每一层的节点就是都调整最底部，那么由于是满二叉树，那么第i层的节点的个数就是2^(i-1),那么其往下调整的高度就是h-i，那么我们计算出每一层的总调整次数，也就是每层的结点个数乘向下的高度，然后累加每一层的总调整个数个数，最后来估算时间复杂度：
$T(N)=2^{h-2}* 1+2^{h-3}*2+2^{h-3}*3+ .....+2^{2}*(h-3)+2^{1}*h-2+2^{0}*(h-1)$
那么我们观察该数列，那么是一个等差乘以等比数列，那么可以采取错位相乘法，也就是整体乘以2，然后再错位相减
$2*T(N)=2^{h-1}*1+2^{h-2}*2+2^{h-2}*3+.....+2^{2}*h+2^{1}*(h-1)$

$T(N)=2^{h-2}* 1+2^{h-3}*2+2^{h-3}*3+ .....+2^{2}*(h-3)+2^{1}*h-2+2^{0}*(h-1)$

然后两个等式相减，然后中间重合部分就是一个等比数列，那么就可以利用等比数列求和公式，最终再根据h=logN，然后得到估计出向下建堆的时间复杂度是O(N)级别的

那么对于向上建堆，这里和向下建堆的估算方法是一样的，同样也会用到错位相减法，那么最终估算出来其时间复杂度是O(N*logN)

那么对于向下调整和向上调整，其实我们可以通过观察就可以粗略的估计出两种方式谁更优秀，因为二叉树越靠近底部的节点的数量更多，那么向下调整对于底部节点来说其调整的次数是很小的，因为其靠近底部，但是对于向上调整来说，底部的大量元素会涉及沿途调整较多的次数，所以向下调整是更优秀的

删除

原理

那么这里对于堆的删除来说，那么堆的删除不能像数组或者链表那样，支持任意位置删除，因为由于堆这个结构本身的特殊性，那么堆顶的元素便具有了意义，那么堆顶的元素代表着该二叉树的最大或者最小的元素，所以堆的删除则是只能删除堆顶，而对于堆的删除来说，那么它删除的目的不是为了舍弃这个元素，而是为了获取到最值，而上文我们说过，堆是用数组来实现的，那么是通过数组下标来建立与二叉树的逻辑映射，那么对于有些读者，那么他知道堆顶元素就是对应数组的第一个位置，那么他采取的做法就是直接挪动元素来删除堆顶的元素，将之后的元素整体向前挪动一个单位

那么我们首先评价一下这种方式，那么数组是通过下标来表示二叉树节点之间的父子关系，那么如果你直接暴力移动，那么就会导致二叉树的节点之间的父子关系混乱，同时也会破坏堆的性质，那么有的读者就会抬杠，他举得这里移动确实会破坏堆结构，那么你移动完之后，在对移动后的所有元素再重新建堆，然后再获取堆顶不就可以了吗

那么这种方式肯定是正确，没有任何问题的，但是缺陷就在效率上，那么这里涉及到了挪动元素，那么注定这个方式的效率是不够优秀

那么这里我们注意，删除了堆顶的元素，而由堆结构我们可以知道，堆的左右子树依然都满足堆性质，那么这里我们就可以利用左右子树的堆性质，而上文说的向下调整就需要左右子树满足堆性质，所以这里我们更为优秀的做法就是这里堆顶与最后一个叶子节点的值进行交换，那么此时由于我们是数组来实现，到时候我们会维护一个size变量来记录有效长度，然后size–，那么此时现在处于有效数据末尾的堆顶就被逻辑上的删除了，而此时原本处于末尾，而现在被交换到堆顶的元素，就会导致整个二叉树是肯定是不满足堆结构的，那么我们就从堆顶开始向下调整就完了，因为除了堆顶，它的左右子树都满足堆性质，那么这就是我们删除的一个原理

实现

那么删除的实现就首先交换元素，然后对堆顶位置向下调整就可以了

	void pop(vector<datatype>& l1){std::swap(l1[0], l1[l1.size() - 1]);adjustDown(l1,0);l1.resize(l1.size() - 1);}

堆排序

那么接下来就是讲解如何用堆进行排序了，我们知道堆有大根堆以及小根堆两种，所以堆排序的第一个环节就是选择哪个堆来实现，那么假设我们要给一个数组中的元素排一个降序，那么我们究竟选择什么堆

那么有的读者自然想到建大堆，因为堆顶为最大元素，获取完堆顶元素后再删除，再建堆在取次大的，那么这个方式可以是可以，那么关键是你得额外开辟一个数组，从前往后放依次放取下的堆顶，那么有没有一种更优秀的方式，也就是不需要额外的数组，直接在原数组的基础上进行排序

能实现原数组的基础上进行排序只能是建小堆，虽然小堆是获取当前最小元素，但是根据我们堆的删除的原理，那么堆顶的元素会与最后一个叶子节点进行交换，那么此时删除过后，那么最小的元素就在最后面，那么接着在对原数组的元素再向下调整建堆，那么重复刚才的操作，那么就能够得到次小然后紧跟在刚才最小数的前面，最终就能得到降序并且还是是在原数组的基础上，不需要额外开辟空间

而同理升序就要建大堆，那么原理就和上面一样，不在多说，那么这里我们再来评估一下堆排序的时间复杂度，那么每次向下调整的时间复杂度是O(logN)，那么总共要有n次,所以堆排的时间复杂度是o(n*logN)，那么这就是关于堆的所有的内容，那么带你全方位回顾了堆

优先级队列

那么再知道了堆这个结构之后，那么这里为什么优先级队列选择用堆实现而不是队列，那么因为堆的性质，那么我们可以在向上以及向下调整中自定义一种比较方式，那么让优先级最高的元素处于堆顶，而对于队列来说，那么你根据优先级调整队列中的位置，那么想必只能一个一个数之间依次比较，那么时间复杂度是o(N^2)才能得到一个优先级队列，而堆的话，根据上文所说的向下调整建堆，只需要O(N),所以这就是为什么选择堆作为优先级队列的底层实现

那么堆是采取数组实现，那么有了之前栈和队列的经验，那么这里我们就只需要利用适配器模式，利用已有的vector，不用我们再自己开辟维护动态数组了，那么对于优先级队列的各种成员函数就是复用已有的容器的成员函数，实现很简单，没必要拿出来再细讲了，能提的就是push与pop成员函数

push函数

那么push函数的实现要用到向上调整建堆而无法用向下调整建堆，因为在插入之前，优先级队列可能已经有元素了并且其一定满足堆性质，那么直接就是利用向上调整即可，无法向下，因为插入的位置都是位于最后一层，那么上文讲解向下调整原理时说过，向下调整只能从倒数第二层开始

	void push(const T& val){_con.push_back(val);adjustUp(_con.size()- 1);}

pop函数

那么pop函数就是交换元素，然后向下调整即可

void pop()
{std::swap(_con[0], _con[_con.size() - 1]);adjustDown(0);_con.resize(_con.size() - 1);
}

而这里优先级队列真正要讲的就是这里的仿函数，那么仿函数是我们优先级队列实现的重点

仿函数

那么我们知道堆有大堆和小堆，那么这里我们创建一个优先级队列，那么有可能建的是大堆也有可能建的是小堆，那么如何实现一个能够同时支持这两个堆的优先级队列呢，那么有的读者想的就是定义两个模板类，分别一个支持大堆，另一个支持小堆，然后再把这两个模板类封装到一起即可，那么这样肯定是可行的，但是我们发现大堆和小堆的核心的代码逻辑不同就在于向上以及向下调整建堆时候父子节点的比较，那么这里我们就可以采取仿函数，那么所谓的仿函数就是在一个类中重载()运算符，那么我们创建一个类的对象，然后调用该运算符重载函数即可，那么这就是所谓的仿函数，其实就是调用一个类的()重载函数，而仿函数名称的由来则就是其调用该运算符重载函数很像调用一个普通函数而不是调用类的成员函数

class node
{int operator()(int x,int y){return x+y;}
};
int main()
{node add;int x=10;int y=20;cout<<add(10,20)<<endl; //你的视角//编译器的视角 :add.operator()(x,y)return 0;
}

在这里插入图片描述

但是由于我们不知道优先级队列中存储的数据类型具体是什么样，所以这里就只能将仿函数定义为模板类，然后根据到时候传进来的参数实例化出相应的类，所以你可以看到优先级队列的第三个模版参数是一个仿函数，那么其默认是less，也就是大堆

template<typename T>
class less
{
public:bool operator()(const T& l1, const T& l2){return l1 > l2;}
};
template<typename T>
class greater
{
public:bool operator()(const T& l1, const T& l2){return l1 < l2;}
};
template<typename T,typename container=std::vector<T>,typename com=less<T>>
class prioriety_queue
{private：container _con;
}；

所以这里的向上调整以及向下调整就需要建立一个仿函数对象compare，然后再调用()运算符重载函数

源码

priority_queue.h

#pragma once
#include<vector>
#include<algorithm>
namespace wz
{template<typename T>class less{public:bool operator()(const T& l1, const T& l2){return l1 > l2;}};template<typename T>class greater{public:bool operator()(const T& l1, const T& l2){return l1 < l2;}};template<typename T,typename container=std::vector<T>,typename com=less<T>>class prioriety_queue{private:container _con;public:void adjustDown(size_t parent){com compare;size_t child = parent * 2 + 1;while (child < _con.size()){int fit_child = child;if (child + 1 < _con.size() &&compare(_con[child+1],_con[child])){fit_child= child + 1;}if (compare(_con[fit_child] , _con[parent])){std::swap(_con[parent], _con[fit_child]);parent = fit_child;child = 2 * parent + 1;}else{break;}}}void adjustUp(size_t child){com compare;size_t parent = (child - 1) / 2;while (child > 0){if (compare(_con[child] , _con[parent])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& val){_con.push_back(val);adjustUp(_con.size()- 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);adjustDown(0);_con.resize(_con.size() - 1);}const T& top(){return _con[0];}bool empty()  {return _con.empty();}size_t size() const{return _con.size();}};
}

priority_queue.cpp:

#include"prioriety_queue.h"
#include<iostream>
using std::cout;
using std::endl;
int main()
{wz::prioriety_queue<int> l1;l1.push(2);l1.push(5);l1.push(4);l1.push(9);l1.push(20);l1.push(1);l1.push(2);while (!l1.empty()){cout << l1.top() <<" ";l1.pop();}return 0;
}