前置知识：

注意：实现堆需要用到完全二叉树的知识，如果未学习，点击了我也没用，因为我还没写

什么是堆？

堆（heap），又叫二叉堆，是一种基于完全二叉树实现的数据结构，它可以实现在堆顶的元素是整个堆里面最大的元素（大根堆），也可以是最小的元素（小根堆），进而获取到整个仪器中的最值的一种数据结构。通过它，我们可以快速获取一组数据中的最值，它的时间复杂度只有O(logn),堆同时也支持删除操作，不过它只能删除堆顶。

图解示范

首先我们先看完全二叉树的节点序号如下，可以发现一个父节点和子节点序号的关系：
设父节点序号为x,那么左子节点的序号为2x，右子节点的序号为2x+1
我们同时也可以知道一个节点x的父节点序号为x/2,（右子节点也是，因为int类型除以2默认向下取整）

首先给出一个堆（这里我们以大根堆为例）

1
2

int w[MAXN];
int tot; //当前堆中节点的个数 

对于插入操作
假如我们插入一个5，我们将其插到数组的最后，作为叶子节点。

如果此时插入的子节点大于其父节点的值，违背了大根堆的性质，那么我们需要堆二叉堆进行修复(modify)操作
即向上比较，如果其大于父节点的值，那么便交换两者的位置.

因为5 > 1 所以与其父节点进行位置交换，然后接着进行修复操作，继续向上比较大小

5 > 4,继续与父节点进行位置交换，然后接着向上进行比较，发现小于它的父节点，所以停止修复
可见整个修复过程是相对二叉堆来讲自下而上的修复。

接着我们来讲删除堆顶的操作，首先我们无法直接删除堆顶，否则二叉堆会分裂为两棵树，修复麻烦巨大。
所以我们寻找一种合适的做法：先把堆顶和堆尾（数组的最后一个数）交换位置

然后我们将交换过去的堆顶在队尾删除。
接着我们发现堆顶的元素是一个较小（甚至最小）的数，违背了大根堆的原则，我们又需要对二叉堆进行修复(repair)
相对于前者的插入修复，这里的删除修复是一种自上而下的修复。
首先比较两个子节点的大小，接着父节点与子节点中较大的一个进行大小的比较，如果小于其中较大的节点，对二者进行交换。
选择其中较大的子节点是为了确保如果进行交换，交换上去的子节点是一个更大的数，这样满足大根堆的性质。
此处,进行修复（交换0和7），然后接着向下判断

,进行修复（交换0和6）

每一步也都要对修复的过程进行判断，如果已经是叶子节点（2x > tot） 那么停止修复，这里满足的就是这种情况
如果出现父节点的值大于两个子节点的值，也停止修复。

这样，我们就完成了删除堆顶操作的修复操作。

代码示范

访问堆顶，很简单，根节点（1）即为最大值

1
2
3
4

int top()
{
	return w[1];
}

修复到的节点序号为x,如果修复过程中x已经是根节点(x == 1)，或者大于其父节点w[x] < w[x/2] 回溯
否则，交换x与父节点的值，然后接着向上递归修复。

1
2
3
4
5
6
7
8
9
10
11

void modify(int x)
{
	if(x == 1 || w[x] < w[x/2]) return;
	swap(w[x],w[x/2]);
	modify(x/2);
}
void push(int x)
{
	w[++tot] = x; //将x加到底部 
	modify(tot); //自底向上递归修复 
}

接下来是删除堆顶操作，详解请看备注
讲一下三目运算符 condition ? x : y condition为布尔型判断，为真返回x，为假返回y

1
2
3
4
5
6
7
8
9
10
11
12

void repair(int x)
{
	if(x*2 > tot) return; //x已经是叶子节点
	int target = x * 2; //target为两个子节点中较大的一个的序号 
	if(x*2+1 <= tot) target = w[x*2] > w[x*2+1] ? x*2 : x*2+1; //三目运算符，target等于较大一个子节点的序号 
	//这里是为了防止只有一个子节点的情况出现，所以提前赋值为2x再进行判断。 
}
void pop()
{
	swap(w[1],w[tot--]); //交换堆顶与堆尾然后删除堆尾
	repair(1) //从根节点开始自上向下修复 
}

自此我们实现了堆的所有操作，如果想要判断是否为空和堆的节点个数，通过tot的值便可以实现，这里不再给出具体的代码。

接下来我们引入一个模板题

堆的模板题

https://www.luogu.com.cn/problem/P3378
这是一道小根堆的模板题，大家可以前往自测，这里不做讲解只给出代码示范

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000007;
int w[MAXN];
int cnt = 0;

int top()
{
	return w[1];
}

void modify(int x)
{
	if(x == 1 || w[x] > w[x / 2]) return;
	swap(w[x],w[x / 2]);
	modify(x / 2);
}


void push(int x)
{
	w[++cnt] = x;
	modify(cnt);
}

void repair(int x)
{
	if(x * 2 > cnt) return;
	int tar = x * 2;
	if(x*2+1 <= cnt) tar = w[x*2] < w[x*2+1]? x*2:x*2+1;
	if(w[x] > w[tar])
	{
		swap(w[x],w[tar]);
		repair(tar);
	}
}

void pop()
{
	if(cnt)
	{
		swap(w[1],w[cnt--]);
		repair(1);
	}
	
}

int main(){
	int n;
	cin>>n;
	while(n--)
	{
		int option;
		scanf("%d",&option);
		if(option == 1)
		{
			int x;
			scanf("%d",&x);
			push(x);
		}
		if(option == 2) printf("%d\n",top());
		if(option == 3) pop();
	}
	return 0;
} 

快速排序（堆排序）

题目描述

将读入的 个数从小到大排序后输出。

输入格式

第一行为一个正整数 。

第二行包含 个空格隔开的正整数 ，为你需要进行排序的数。

输出格式

将给定的 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例输入

1
2

5
4 2 4 5 1

样例输出

1

1 2 4 4 5

这是一个通过堆排序实现快排（用小根堆）的模板题，原理就是不断弹出堆顶，来从小到大输出数据。
大家可以前往洛谷进行自测 点我跳转
对比上一道题，这道题的做法就是将一组数据不断插入堆顶，然后输出一个，pop一个，进行n次操作。
下面是伪代码示范

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<bits/stdc++.h>
using namespace std;
......
int main(){
	int n,x;
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		cin>>x;
		push(x);
	}
	for(int i = 1; i <= n; i++)
	{
		cout<<top()<<" ";
		pop();
	}
	return 0;
}

接着我们给出最后一道例题

[NOIP2004 提高组] 合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 种果子，数目依次为 ， ， 。可以先将 、 堆合并，新堆数目为 ，耗费体力为 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 ，耗费体力为 。所以多多总共耗费体力 。可以证明 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 ，表示果子的种类数。

第二行包含 个整数，用空格分隔，第 个整数 是第 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 。

样例输入

1
2

3 
1 2 9

样例输出

1

15

通过题目描述我们不难看出，先合并的石子在后面会参与到后续的合并过程，这就导致它的重量会在后面反复被消耗，即先合并的果子后面其被搬运的次数越多，通过贪心策略我们不难得知，较小的体力消耗的次数越多我们最后体力消耗的总数越少，所以我们实现一个小根堆，每次连续取出两个小根堆堆顶的值，然后再将两个堆顶的和插入到堆中，直到堆为空。
接下来给出伪代码

1
2
3
4
5
6
7

while(tot > 1) //tot为2时搬运最后一次，将最后两堆石子合在一起 
{
	x = top(); pop();
	y = top(); pop();
	push(x + y);
	sum+=(x+y);
}

优先队列（priority_queue）

优先队列（priority_queue）是一种由STL操作的特殊的队列，它可以实现队列的功能，在此之上，实现队首是整个队列中的最大值（或最小值）
它的底层逻辑是堆，需要包含<queue>头文件或者万能头，但是它只能访问队首（也就是最值）。
接下里我们给出使用方法

1
2
3
4
5

priority_queue <int> q : 新建一个内部为int类型的优先队列q，默认q为大根堆
priority_queue <int,vector <int> ,greater <int> > q : 新建一个小根堆 最后两个> >用空格隔开,否则与"右移>>"写法重复 
q.top() : 查询优先队列最值（堆顶）
q.pop() : 弹出堆顶
q.push(k) : 将x插入优先队列 

这样我们再回去做合并石子,并用STL操作优先队列来完成这道题目
给出代码示范

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int ans = 0;
	priority_queue<int, vector<int>, greater<int> > q;
	for(int i = 1; i <= n; i++)
	{
		int k;
		cin>>k;
		q.push(k);
	}
	while(!q.empty())
	{
		int temp = q.top();
		q.pop();
		temp+=q.top();
		q.pop();
		ans+=temp;
		if(!q.empty()) q.push(temp);
	}
	cout<<ans;
	return 0;
}