前言
大前天（2019/1/19）作者回到机房，发现自己咕咕咕半个月后被学长嘲讽了，于是去找Herself32学堆……
初始约定
在下文堆的STL实现中，很多时候会出现(begin , end)
这表示一段数组上的区间：从begin 到 end
其中，begin为开头，end为结尾。
就像下图：
但值得一提的是，begin在这个区间内，但end不在。
何为堆？
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
——百度百科
……
度娘越来越坏了，只会装高冷。还是看看通俗易懂的解释吧。
事实上，堆就是一颗完全二叉树，但它还要满足一个条件：
- 堆中的每个节点不论怎么调整，都不小于(或不大于)它的父节点。
根据这个条件，我们就可以把堆分成两种：大根堆和小根堆。
就像下图，就是两个典型的小根堆和大根堆：
小根堆：
大根堆：
怎么样，是不是很懵逼？
那是因为我忘了告诉你小根堆和大根堆的定义了。
我们将根节点最大的堆叫做大根堆， 将根节点最小的堆叫做小根堆。
但要注意：必须是每一颗子树都要满足条件，即每一颗子树的每一个节点都要比它的父节点大（或小）。
这是按根节点的大小来分，如果按操作种类来分，那么常见的堆有二叉堆、斐波那契堆等。
如何存储一个堆？
看到这，你可能要问了：“既然这样，怎么存储一个堆呐？”
别急，慢慢看就知道了。
我们知道，堆是一种线性的数据结构，有唯一的后继。
所以
开一维数组模拟啊
学过完全二叉树的同学都知道这样一句话：在完全二叉树中，一个节点的编号为x，则它的左儿子编号为2x， 右儿子编号为2x + 1。
在前面我已经说过，堆也是一颗完全二叉树。
因此，堆也满足这个性质。
如果我们定义一个名为Heap[]的数组表示堆，那么
(小根堆)。
(大根堆)。
同时，我们还可以看出，堆顶元素一定是最大（或最小）元素。
堆的操作。
现在你可能要问：“这么麻烦的堆，有什么用吗？”
当然是拿来怼人啦
咳咳，一个堆支持以下4种操作：
- 插入一个节点
- 删除堆顶元素
- 输出堆顶元素
- 堆排序
在讲这4种操作之前，我们先来看看堆的两种基本操作：Shiftup & Shiftdown。
（ps.所有的操作都基于这两种基本操作）
Shiftup（ps.大根堆）
众所周知，大根堆中的每一个父节点都大于它的任意子节点
因此，我们在插入一个节点后需要把它与它的父节点比较
如果它比它的父节点大，则交换，继续比较。
否则，则退出循环。
刚不过就认怂呗
来看这个图：
此时，我们在树的最后插入一个元素36（ps.插入元素时要在树的最后插入）：
现在开始Shiftup, 此时36与他的父节点19比较，发现自己比他大，进行交换。
交换后的36与它的父节点26比较，发现自己比他大，进行交换。
最后36与90比较，发现比不过了，于是认怂，break掉循环，结束。
伪代码如下：
void Shiftup(int x){ //x为节点下标
while（x不是根节点）{
if（Heap[x] 大于它的父节点）{
将Heap[x]与它的父节点交换;
x = x / 2; //父节点的下标为子节点下标除以2
}
else{
break;
}
}
} Shiftdown (ps.大根堆)
同理，有上浮就会有下沉。可以把Shiftdown看成Shiftup的反过程。
唯一不同在于，Shiftdown有两个比较对象，分别是他的左儿子和右儿子。
在交换之前，需要先找到它的左儿子和右儿子中较大的那一个。
来看这个图：
此时，我们删除堆顶的90，成了下面这个样子：
最后一个元素会上来补位，就成了这样：
现在，Shiftdown开始了。
先将36与17比较，发现36更大，于是把36与19交换，成了下图的样子：
再把25与26比较，发现26更大，于是把26与19交换，成了这样：
现在，19已经没有子节点了。于是我们可以break掉循环，结束Shiftdown了
伪代码如下
void shiftdown(int x){
int maxn,number;
while(Heap[x]有子结点){
maxn = max(它的左子结点 ， 它的右子结点);
if(maxn == 左子结点){
number = 左子结点的下标;
}
else if(maxn ==右子节点){
number = 右子节点的下标;
}
if(Heap[x] < a[number]){
将Heap[x]与相对较小的子结点交换
x = number;
}
else{
break;
}
}
} （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不就行了！
就像下边
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp (int a, int b){
return a > b;
}
int n, a[10001];
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
make_heap(&a[1], &a[n], cmp);
……
return 0;
} 一个小根堆就这么建成了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<int>后面一定要有一个空格</int>，否则的话会被编译器识别为右移运算符“>>”
现在，我们就来讲讲优先队列的几种操作。
push
无疑，这个函数可以把一个元素加入优先队列，和队列中的push用法一样。
代码如下：
priority_queue<int > Q; int a; Q.push(a);
top
这个函数可以获取队列中的最大或最小元素，即堆顶。但它并不会删除堆顶元素。
代码如下：
priority_queue<int > Q; int a = Q.top();
pop
这个函数可以弹出堆顶元素，即删除堆顶元素。
代码如下：
priority_queue<int > Q; Q.pop();
empty
这个函数可以判断堆是否为空，返回值是一个bool型变量。
如果说队列为空，则返回true，否则返回false
代码如下：
priority_queue<int > Q; bool a; a = Q.empty;
附件：堆[手写模板]
代码描述： 见洛谷P3378.
源代码（ps.防作弊已开启）：
#include<iostream>
using namespace std;
int n,x,len = 1,a[1000001],ans[1000001];
void shiftup(int x){
while(x > 1){
if(a[x] < a[x / 2]){
swap(a[x] , a[x / 2]);
x = x / 2;
}
else{
break;
}
}
}
void shiftdown(int x){
int minn,number;
while(x * 2 + 1 <= len){
minn = min(a[x * 2 + 1] , a[x * 2]);
if(minn == a[x * 2 + 1]){
number = x * 2 + 1;
}
else if(minn == a[x * 2]){
number = x * 2;
}
if(a[x] > a[number]){
swap(a[x] , a[number]);
x = number;
}
else{
break;
}
}
}
void push(int x){
a[len] = x;
len ++;
shiftup(len - 1);
}
int Return(){
return a[1];
}
void Delete(){
a[1] = a[len - 1];
a[len - 1] = 0;
len --;
shiftdown(1);
}
int main(){
int x,s;
int c = 1;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> x;
if(x == 1){
cin >> s;
push(s);
}
else if(x == 2){
ans[c] = Return();
c ++;
}
else if(x == 3){
Delete();
}
}
for(int i = 1; i <= c - 1; i++){
cout << ans[i] <<endl;
}
return 0;
} 附件2 堆的STL实现
代码描述
这段代码是堆的STL实现的基本格式，注释会对代码进行解释，堆为小根堆。
源代码
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a, int b){//比较函数
return a > b;
}
int n , a[10001];
int main(){
cin >> n; // 输入6
for(int i = 1; i <= n; i++){
cin >> a[i]; //输入2 3 5 8 1 9
}
make_heap(&a[1] , &a[n] , cmp);
//此时，堆内元素为1 2 5 8 3 9
cin >> a[n]; //输入4
push_heap(&a[1] , &a[n + 1] , cmp);
//此时，堆内元素为1 2 4 8 3 5 9
pop_heap(&a[1] , &a[n + 1] , cmp);
//此时，堆内元素为2 3 4 8 9 5
sort_heap(&a[1] , &a[n + 1] , cmp);
//结果肯定是有序的……
for(int i = 1; i <= n; i++){
cout << a[i] << " ";
}
return 0;
} 附件3 优先队列的STl实现
这份代码是优先队列的STL实现，同时也是洛谷P1090的标程，
因此，本代码开启防作弊功能。
但不要担心，优先队列的模板部分是没有错误的。
#include<iostream>
#include<queue>
using namespace std;
void work(){
return ;
}
priority_queue<int , vector<int> , greater<int> > Q;
int ans = 0;
int main(){
work();
int n , a;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a;
Q.push(a);
}
while(Q.size() >= 2){
int x = Q.top();
Q.pop();
int y = Q.top();
Q.pop();
ans += x + y;
Q.push(x + y);
}
cout << ans <<endl;
return 0;
} 更新日志
2019.2.10 更新了标签，修改了少量错别字
2019.2.23 更新了STL部分
2019.3.30 更新了priority_queue部分
……
京公网安备 11010502036488号