一、堆是什么？什么是小根堆？
堆其实就是一棵完全二叉树，那么什么是完全二叉树，如下图：
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
那么什么是小根堆？
小根堆是堆的一种，对于小根堆而言，一个节点的值总比它的左节点的值要小，也比它的右节点的值要小，通俗莱昂，可以把小根堆看作是一个土堆，最上面的沙土的数量最少。
二、堆的三大基本操作
-
下沉操作（down操作）
down操作中传的值代表是第几个节点，而不是某一个元素的值
让这个节点从当前位置下沉
void down(int u) {
int t; //t用来存放当前值和当前值的左儿子和当前值的右儿子中的最小值
t = u;//先让t等于u这个节点
if(u * 2 <= sz && h[u * 2] < h[t]) t = 2 * u;//判断t这个点和t的左儿子的值的大小
if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = 2 * u + 1;//判断t这个点和t的右儿子的值的大小
if(u != t) {//如果节点的值的大小不一样或者说 这个时候 应该下沉
swap(h[u], h[t]);//交换两个节点对应的值
down(t);//递归向下处理第t个点
}
}
- 上浮操作（up操作）
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u /= 2;
}
}
- 自定义交换
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
这里有两个数组，ph[]和hp[]
ph[m]=n 代表的是第m个插入的点在堆中的第n个点（堆数组的下标）
hp[n] = m代表的是堆中的第n个点是插入的第m个点
不难发现，其实这两个数组是一一对应，相互连接的，所以我们只要改变其中一个数组，另一个数组也要去改变
那么为什么需要这两个数组呢？
1.我们可以看到下面模拟堆中第四个和第五个操作，都是对第k个插入的元素进行操作
比如说我们前面已经插入6个元素了，现在想删除第4个插入的元素，问题来了，我们怎么找到第4个插入的元素，所以ph数组应运而生，ph的下标的值代表的是第几个插入的数，ph的值代表的是插入的数在堆中的位置（堆数组的下标），通过ph数组就可以找到我们之前插入的值，这就是ph数组的作用
2.那么为什么还需要ph中的值交换呢？
这是因为我们在做交换的时候，是让h[a]和h[b]交换，我们交换的是堆中a点的值和堆中b点的值，只是让它们对应的值交换，但是堆中a点和b点并没有交换，也就是引用没有交换。如果是这样的，一旦发生交换，那么通过ph数组找到的堆中的点就不是刚开始堆中的点了，因为数值发生了变化；所以ph数组的值也得交换。
3.那么又为什么需要hp数组呢？
这是因为我们在heap_swap中传入的是堆数组的下标（a，b），那么你可能会说，那这样就不需要让ph数组交换了呀，直接让a和b交换不就行了。这样想是对的，但是这样的话，ph就没用了呀，但是我们刚刚得出了结论是ph是必需的，所以不能让a和b直接交换。所以现在的情况是ph[] = a, ph[] = b，我们可以看到，我们只知道堆数组的下标，由此不能确定ph数组的下标，也就无法让ph数组实现交换，所以hp数组应运而生，hp数组的下标是堆中的点（堆数组的下标），hp的值是第几个插入的数，与ph相反且一一对应，那么我们就可以通过传入的堆数组的下标a和b来确定ph的下标值，也就是hp[a], hp[b]，所以我们最后交换的是ph[hp[a]]和ph[hp[b]]，一旦ph数组发生交换，那么hp数组也要发生交换。
三、手写一个堆
heap是用于存放堆的数组，size表示当前数组的大小，也表示堆中元素的数量
-
插入一个数
heap[ ++ size ] = x; up(size);
把这个数先插入到数组的最后，然后上浮最后一个节点
-
求集合中的最小值
heap[1];
取数组的第一个元素，也就是堆的最高点
-
删除最小值
heap[1] = heap[size]; size--; down(1)
先把数组的第一个元素的值和最后一个元素的值互换，然后数组的大小减一
因为最后一个元素的值比第一个元素的值要大，所以互换值后，需要让互换后，数组的第一个点下沉，以满足小根堆
-
删除任意一个元素
heap[k] = heap[size]; size--; down(k); up(k)
过程基本同3
先把某个元素的值与最后一个元素的值互换，然后数组的大小减一
因为无法确定互换后那个元素的值与上下元素值的大小关系，所以应该先要用if语句来判断一下是要上浮还是下沉，但是其实没必要，让上浮和下沉都执行一次就可以了（执行孙顺序没有关系），不需要判断。
-
修改任意一个元素
heap[k] = x; down(k); up(k)
将某一个元素的值改变后，无法判断改变后的值与上下元素值的大小关系，所以让上浮和下沉都执行一次就可以了（执行顺序没有关系）
四、模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第 k 个插入的数；C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105 −109≤x≤109 数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
代码如下：
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 100010;
int h[N], ph[N], hp[N], sz;
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u /= 2;
}
}
int main()
{
int n, m = 0;
scanf("%d", &n);
while (n -- )
{
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I"))
{
scanf("%d", &x);
sz ++ ;
m ++ ;
ph[m] = sz, hp[sz] = m;
h[sz] = x;
up(sz);
}
else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, sz);
sz -- ;
down(1);
}
else if (!strcmp(op, "D"))
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, sz);
sz -- ;
up(k);
down(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
return 0;
}
五、堆排序
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤105 1≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N];//h[N]是一个二叉树，用来存放堆
int sz;//表示数组的大小，也表示元素的个数
int n, m;
void down(int u) {
int t; //t用来存放当前值和当前值的左儿子和当前值的右儿子中的最小值
t = u;
if(u * 2 <= sz && h[u * 2] < h[t]) t = 2 * u;
if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = 2 * u + 1;
if(u != t) {
swap(h[u], h[t]);
down(t);
}
}
int main() {
scanf("%d%d", &n, &m);
sz = n;
for(int i=1; i<=n; i++) scanf("%d", &h[i]);
for(int i=n/2; i; i--) down(i);
while(m--) {
printf("%d ", h[1]);
h[1] = h[sz];
sz--;
down(1);
}
return 0;
}
