中科医院曝光 http://www.csjkc.com/yydt/637.html二叉堆是一种基础数据结构，主要应用于求出一组数据中的最大最小值。C++的STL中的优先队列就是使用二叉堆。不过初赛经常考二叉堆的原理。事实上支持的操作也是挺有限的（相对于其他数据结构而言），也就插入，查询，删除这一类。对了这篇文章中讲到的堆都是二叉堆，而不是斜堆，左偏树，斐波那契堆什么的我都不会啊。一.堆的性质1.堆是一颗完全二叉树2.堆的顶端一定是“最大”，最小”的，但是要注意一个点，这里的大和小并不是传统意义下的大和小，它是相对于优先级而言的，当然你也可以把优先级定为传统意义下的大小，但一定要牢记这一点，初学者容易把堆的“大小”直接定义为传统意义下的大小，某些题就不是按数字的大小为优先级来进行堆的操作的（但是为了讲解方便，下文直接把堆的优先级定为传统意义下的大小，所以上面跟没讲有什么区别？）3.堆一般有两种样子，小根堆和大根堆，分别对应第二个性质中的“堆顶最大”“堆顶最小”，对于大根堆而言，任何一个非根节点，它的优先级都小于堆顶，对于小根堆而言，任何一个非根节点，它的优先级都大于堆顶（这里的根就是堆顶啦qwq）来一张图了解一下堆（这里是小根堆）（原谅我丑陋无比的图）不难看出，对于堆的每个子树，它同样也是一个堆（因为是完全二叉树嘛）二.堆的操作1.插入假设你已经有一个堆了，就是上面那个这个时候你如果想要给它加入一个节点怎么办，比如说0？先插到堆底（严格意义上来说其实0是在5的左儿子的，图没画好放不下去，不过也不影响）然后你会发现它比它的父亲小啊，那怎么办？不符合小根堆的性质了啊，那就交换一下他们的位置交换之后还是发现不符合小根堆的性质，那么再换还是不行，再换好了，这下就符合小根堆的性质了，是不是顺眼很多了？（假的，图越来越丑，原谅我不想再画）事实上堆的插入就是把新的元素放到堆底，然后检查它是否符合堆的性质，如果符合就丢在那里了，如果不符合，那就和它的父亲交换一下，一直交换交换交换，直到符合堆的性质，那么就插入完成了2.删除把0插入完以后，忽然你看这个0不爽了，本来都是正整数，怎么就混进来你这个0？于是这时候你就想把它删除掉怎么删除？在删除的过程中还是要维护小根堆的性质如果你直接删掉了，那就没有堆顶了，这个堆就直接乱了，所以我们要保证删除后这一整个堆还是个完好的小根堆首先在它的两个儿子里面，找一个比较小的，和它交换一下，但是还是没法删除，因为下方还有节点，那就继续交换还是不行，再换再换好了，这个碍眼的东西终于的下面终于没有节点了，这时候直接把它扔掉就好了这样我们就完成了删除操作，但是在实际的代码操作中，并不是这样进行删除操作的，有一定的微调，代码中是直接把堆顶和堆底交换一下，然后把交换后的堆顶不断与它的子节点交换，直到这个堆重新符合堆性质（但是上面的方式好理解啊）手写堆的删除支持任意一个节点的删除，不过STL只支持堆顶删除，STL的我们后面再讲3.查询因为我们一直维护着这个堆使它满足堆性质，而堆最简单的查询就是查询优先级最低/最高的元素，对于我们维护的这个堆heap，它的优先级最低/最高的元素就是堆顶，所以查询之后输出heap[1]就好了一般的题目里面查询操作是和删除操作捆绑的，查询完后顺便就删掉了，这个主要因题而异。三.堆的STL实现这年头真的没几个人写手写堆（可能有情怀党？）一是手写堆容易写错代码又多，二是STL直接给我们提供了一个实现堆的简单方式：优先队列手写堆和STL的优先队列有什么区别？没有区别速度方面，手写堆会偏快一点，但是如果开了O2优化优先队列可能会更快；代码实现难度方面：优先队列完爆手写堆这两方面综合起来，一般都是用STL的优先队列来实现堆，省选开O2啊至于为什么前面讲堆的操作时用手写堆，好理解嘛，最好先根据上面的代码和图理解一下堆是怎么实现那些操作的，再来看一下下面的STL的操作定义一个优先队列：首先你需要一个头文件：#includequeuepriority_queueintq;//这是一个大根堆qpriority_queueint,vectorint,greaterintq;//这是一个小根堆q//注意某些编译器在定义一个小根堆的时候greaterint和后面的要隔一个空格，不然会被编译器识别成位运算符号优先队列的操作：q.top()//取得堆顶元素，并不会弹出q.pop()//弹出堆顶元素q.push()//往堆里面插入一个元素q.empty()//查询堆是否为空，为空则返回1否则返回0q.size()//查询堆内元素数量常用也就这些，貌似还有其他，不过基本也用不到，知道上面那几个也就可以了不过有个小问题就是STL只支持删除堆顶，而不支持删除其他元素但是问题不大，开一个数组del，在要删除其他元素的时候直接就标记一下del
=1，这里的下标是元素的值，然后在查询的时候碰到这个元素被标记了直接弹出然后继续查询就可以了（前两天刚从学长处get这个姿势）另外因为STL好写，下面堆的应用全部都会采用STL的代码实现（懒啊，如果有放代码的话）这里补一下重载运算符在STL的优先队列中应用到的知识重载运算符是什么？把一种运算符变成另外一种运算符（注意，都必须是原有的运算符），比如把号重载成号，这个东西学过STL中的sort的同学应该会比较熟悉这个在优先队列中有什么用处呢？之前我们就讲到了，大根堆，小根堆的“大”和“小”都不是传统意义下的“大”和“小”，重载运算符在STL的优先队列中就是用来解决这种“非传统意义的‘大’和‘小’”的现在你有一个数列，它有权值和优先级两种属性，权值即该数的大小，优先级是给定的，现在要你按照优先级的大小从小到大输出这个数列这不是Treap吗？这不是sort吗？以上两个东西都可以用来实现这道题（逃，而且就实用性而言，sort用来解决这道题是最方便的，但是我们现在要讲的做法是使用堆排序的方式来解决这道题（堆排序是什么？下文堆的应用中有提到）首先应该想得到结构体，我们定义一个结构体但是使用传统做法是行不通的，在小根堆中是通过比较数的大小来确定各个元素在堆中的位置的，但是对于这个a数组，你是要对比权值val的值，还是要对比优先级rnd的值？这时候重载运算符就派上用场了我们在结构体里面再加3行东西这个玩意为什么要这么写呢？首先这个玩意是bool类型的，因为你只需要判断这两个是大，还是小；然后，要重载运算符就必须加一个operator这个玩意，不然计算机怎么知道你要干嘛？后面接一个你要重载的运算符，这里是“”，再后面的括号里面的东西则是你要比较的数据类型，这里是数据类型为node，并且加了一个指针，将对这个x的修改同步到你实际上要修改的数据那里。然后就是记得加那两个const然后两个大括号里面就是你重载的内容了，这里是把比较数的大小的小于号，重载成比较node这个数据类型里面的优先级的大小这个玩意讲的比较多，主要是因为是一个很难懂的东西（对我来说？反正当时学的时候就是感觉很晦涩难懂，这里就尽量写详细一点，给和当初的我一样的萌新看一下）而且在实际中，这个东西的用处也很大，就说在堆里面的应用，在NOIP提高，省选的那个级别，就绝对不可能考裸的堆的，往往你要比较的东西就不是数的大小了，而是按照题目要求灵活更改，这时候重载运算符就帮得上很大忙了这也就是为什么我在前面反复强调，堆里面的大小，并非传统意义下的大小。四.堆的复杂度因为堆是一棵完全二叉树，所以对于一个节点数为n的堆，它的高度不会超过log2n所以对于插入，删除操作复杂度为O(log2n)查询堆顶操作的复杂度为O(1)五.堆的应用1.堆排序其实就是用要排序的元素建一个堆（视情况而定是大根堆还是小根堆），然后依次弹出堆顶元素，最后得到的就是排序后的结果了但是裸的并没有什么用，我们有sort而且sort还比堆排快，所以堆排一般都没有这种模板题，一般是利用堆排的思想，然后来搞一些奇奇怪怪的操作，第2个应用就有涉及到一点堆排的思想2.用两个堆来维护一些查询第k小/大的操作洛谷P黑匣子利用一个大根堆一个小根堆来维护第k小，并没有强制在线不强制在线，所以我们直接读入所有元素，枚举询问，因为要询问第k小，所以把前面的第k个元素都放进大根堆里面，然后如果元素数量大于k，就把堆顶弹掉放到小根堆里面，使大根堆的元素严格等于k，这样这次询问的结果就是小根堆的堆顶了（前面k-1小的元素都在大根堆里面了）。记得在完成这次询问后重新把小根堆的堆顶放到大根堆里面就好。洛谷P合并果子直接从所有果子中找到最小堆最小的果子，合并之后再放入堆中。为了不占太多篇幅就不粘Code了其他应用之后再补本文发布于洛谷日报，特约作者：henry_y原文