堆?怼?
前言
大前天(2019/1/19)作者回到机房,发现自己咕咕咕半个月后被学长嘲讽了,于是去找Herself32学堆……
初始约定
在下文堆的STL实现中,很多时候会出现(begin , end)
这表示一段数组上的区间:从begin 到 end
其中,begin为开头,end为结尾。
就像下图:
但值得一提的是,begin在这个区间内,但end不在。
何为堆?
堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
——百度百科
……
度娘越来越坏了,只会装高冷。还是看看通俗易懂的解释吧。
事实上,堆就是一颗完全二叉树,但它还要满足一个条件:
- 堆中的每个节点不论怎么调整,都不小于(或不大于)它的父节点。
根据这个条件,我们就可以把堆分成两种:大根堆和小根堆。
就像下图,就是两个典型的小根堆和大根堆:
小根堆:
大根堆:
怎么样,是不是很懵逼?
那是因为我忘了告诉你小根堆和大根堆的定义了。
我们将根节点最大的堆叫做大根堆, 将根节点最小的堆叫做小根堆。
但要注意:必须是每一颗子树都要满足条件,即每一颗子树的每一个节点都要比它的父节点大(或小)。
这是按根节点的大小来分,如果按操作种类来分,那么常见的堆有二叉堆、斐波那契堆等。
如何存储一个堆?
看到这,你可能要问了:“既然这样,怎么存储一个堆呐?”
别急,慢慢看就知道了。
我们知道,堆是一种线性的数据结构,有唯一的后继。
所以
开一维数组模拟啊
学过完全二叉树的同学都知道这样一句话:在完全二叉树中,一个节点的编号为x,则它的左儿子编号为2x, 右儿子编号为2x + 1。
在前面我已经说过,堆也是一颗完全二叉树。
因此,堆也满足这个性质。
如果我们定义一个名为Heap[]的数组表示堆,那么
$Heap[x] \leq Heap[2x] \& Heap[2x + 1] $(小根堆)。
$Heap[x] \geq Heap[2x] \& Heap[2x + 1] $(大根堆)。
同时,我们还可以看出,堆顶元素一定是最大(或最小)元素。
堆的操作。
现在你可能要问:“这么麻烦的堆,有什么用吗?”
当然是拿来怼人啦
咳咳,一个堆支持以下4种操作:
插入一个节点
删除堆顶元素
输出堆顶元素
堆排序
在讲这4种操作之前,我们先来看看堆的两种基本操作:Shiftup & Shiftdown。
(ps.所有的操作都基于这两种基本操作)
Shiftup(ps.大根堆)
众所周知,大根堆中的每一个父节点都大于它的任意子节点
因此,我们在插入一个节点后需要把它与它的父节点比较
如果它比它的父节点大,则交换,继续比较。
否则,则退出循环。
刚不过就认怂呗
来看这个图:
此时,我们在树的最后插入一个元素36(ps.插入元素时要在树的最后插入):
现在开始Shiftup, 此时36与他的父节点19比较,发现自己比他大,进行交换。
交换后的36与它的父节点26比较,发现自己比他大,进行交换。
最后36与90比较,发现比不过了,于是认怂,break掉循环,结束。
伪代码如下:
void Shiftup(int x){ //x为节点下标 |
Shiftdown (ps.大根堆)
同理,有上浮就会有下沉。可以把Shiftdown看成Shiftup的反过程。
唯一不同在于,Shiftdown有两个比较对象,分别是他的左儿子和右儿子。
在交换之前,需要先找到它的左儿子和右儿子中较大的那一个。
来看这个图:
此时,我们删除堆顶的90,成了下面这个样子:
最后一个元素会上来补位,就成了这样:
现在,Shiftdown开始了。
先将36与17比较,发现36更大,于是把36与19交换,成了下图的样子:
再把25与26比较,发现26更大,于是把26与19交换,成了这样:
现在,19已经没有子节点了。于是我们可以break掉循环,结束Shiftdown了
伪代码如下
void shiftdown(int x){ |
(ps.至于插入和删除一个元素,自己想想也就知道了。在这里不再专门讲述)其实是作者太懒
输出堆顶元素
cout << Heap[1]; |
不知道为啥的请回看[如何存储一个堆]部分。
堆排序
如果是升序排序,就建一个小根堆持续弹出。
降序就建一个大根堆持续弹出即可。
堆的STL
本部分仅适合c++选手食用,Pascal & C选手请自觉跳过.(
怕你们怀疑自己选错语言)
众所周知,cpp为我们提供了一个很人性化的模板库——STL
那么……
堆在STL中有没有可以调用的模板呐?
答案是肯定的。
在STL中,堆有4种操作,分别为make_heap(); pop_heap(); push_heap(); sort_heap(); 它们都在algorithm库中
下面,我们就来深入研究一下这4种操作
make_heap
光通过字面应该也能理解,这个函数是用来建立一个堆的。
格式为make_heap(begin , end);
默认建立的是一个大根堆哦。
既然如此,如果要建立一个小根堆该怎么办呐?
写一个比较函数cmp不就行了!
就像下边
|
一个小根堆就这么建成了QVQ
但一定注意,cmp是放在end后边的。
pop_heap
这个函数可以将堆中的堆顶元素弹出。
就好像前面的Shiftdown一样
格式为pop_heap(begin , end , cmp); (大根堆不加cmp)
push_heap
既然有弹出,那就一定会有加入
而这个函数就可以在堆中加入一个元素。
就像前面的Shiftup。
格式为push_heap(begin , end , cmp); (大根堆不加cmp)
sort_heap
显然,这是一个堆排序函数。
堆排序在实际排序时应用不多,但一些优化必须使用。
格式为sort_heap(begin , end , cmp); (大根堆不加cmp)
但值得一提的是,堆排之后,这个堆就不是一个合法的堆了。
priority_queue
想必大家都已经学会队列了吧 没学过的请点击这里
现在我们要讲的就是队列的一种特殊形式:优先队列
那么,什么是优先队列呐?
学过队列的同学都知道,队列就像公平的队伍一样,从后面进,前面出,出队的顺序与节点的权值无关
而优先队列,就像一个不太公平的队伍。总是让当前权值最大或最小的节点先出队。
所以……
这不就是一个典型的堆嘛QAQ
但别忘了,优先队列也是队列,所以它的所有操作都包含在queue库中
优先队列的定义如下:
priority_queue<int > Q; //定义一个名为Q的最大优先队列,队列里的数据类型为int型 |
但是,优先队列默认为最大优先队列,即大根堆。如果我们要定义一个最小优先队列,写法就会不同。
priority_queue<int , vector<int> , greater<int> > Q; //定义一个名为Q的最小优先队列,数据类型为int |
随带提一句,greater
现在,我们就来讲讲优先队列的几种操作。
push
无疑,这个函数可以把一个元素加入优先队列,和队列中的push用法一样。
代码如下:
priority_queue<int > Q; |
top
这个函数可以获取队列中的最大或最小元素,即堆顶。但它并不会删除堆顶元素。
代码如下:
priority_queue<int > Q; |
pop
这个函数可以弹出堆顶元素,即删除堆顶元素。
代码如下:
priority_queue<int > Q; |
empty
这个函数可以判断堆是否为空,返回值是一个bool型变量。
如果说队列为空,则返回true,否则返回false
代码如下:
priority_queue<int > Q; |
附件:堆[手写模板]
代码描述: 见洛谷P3378.
源代码(ps.防作弊已开启):
|
附件2 堆的STL实现
代码描述
这段代码是堆的STL实现的基本格式,注释会对代码进行解释,堆为小根堆。
源代码
|
附件3 优先队列的STl实现
这份代码是优先队列的STL实现,同时也是洛谷P1090的标程,
因此,本代码开启防作弊功能。
但不要担心,优先队列的模板部分是没有错误的。
|
更新日志
2019.2.10 更新了标签,修改了少量错别字
2019.2.23 更新了STL部分
2019.3.30 更新了priority_queue部分
……