目录
- 一、堆的数据结构
- 二、堆的操作方法
- 往下调整的示意图
- 往上调整的示意图
- 相关功能的实现思路
- 1.插入一个数
- 2.求最小值
- 3.删除最小值
- 4.删除任意一个元素
- 5.修改任意一个元素
- 三、堆的实战运用
- 堆排序
- 模拟堆
一、堆的数据结构
堆是一个完全二叉树：除了最后一层结点以外，上面的每一层都是满的。最后一层的结点是从左到右排布的。
小根堆：每一个点都是小于左右子节点的，所以根节点就是树中最小值或者叫小顶堆。(递归定义)
存储方式：全新的存储方式，用一维数组来存。因为是完全二叉树，所有数据的下标是有规则可以找到的。
- 父节点
x/2 - 节点
x - 左子节点
2x - 右子节点
2x+1
注意下标从1开始的（符合节点之间的数学规律）
二、堆的操作方法
往下调整的示意图
down(x) 往下调整
往上调整的示意图
up(x) 往上调整
相关功能的实现思路
1.插入一个数
heap[++size] = x;
up(sz); // 往上调整
2.求最小值
heap[1];
3.删除最小值
heap[1] = heap[size--];
down(1);
4.删除任意一个元素
heap[k] = heap[sz--];
// 只执行其中之一 ：大了向下走 小了向上走
down(k);
up(k);
5.修改任意一个元素
heap[k] = x;
down(k);
up(k);
三、堆的实战运用
堆排序
题目描述：
输入一个长度为
n
n
n 的整数数列，从小到大输出前
m
m
m 小的数。
输入格式：
第一行包含整数
n
n
n 和
m
m
m。第二行包含
n
n
n 个整数，表示整数数列。
输出格式：
共一行，包含
m
m
m 个整数，表示整数数列中前
m
m
m 小的数。
数据范围：
1
≤
m
≤
n
≤
1
0
5
1≤m≤n≤10^5
1≤m≤n≤105
1 ≤ 1≤ 1≤ 数列中元素 ≤ 1 0 9 ≤10^9 ≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
tip：
当建树时应从
n
/
2
n/2
n/2的位置开始向上进行down(x)操作，因为根节点无需往下调整，同时其时间复杂度为
O
(
n
)
O(n)
O(n)。
由于根节点为堆的最小值，所以最后询问操作时，打印一次堆最小值，同时删除。
除此之外使用 for (int i = 1; i <= n; i++) up(i);时间复杂度为
o
(
n
l
o
g
n
)
o(nlogn)
o(nlogn)的这种方法也是可以的。
由于堆为完全二叉树，其高度为 l o g 2 n log_2n log2n层，递归版的down(x)的时间复杂度为 o ( l o g n ) o(logn) o(logn)，所以没必要将down(x)改为循环。
代码实现：
const int N = 1e5 + 10;
int h[N], cnt;
void down(int x)
{
int t = x;
// 注意此处不能使用else if
// 每次左右子节点要分别进行一次条件判定
if (x * 2 <= cnt && h[x * 2] < h[t]) t = x * 2;
if (x * 2 + 1 <= cnt && h[x * 2 + 1] < h[t]) t = x * 2 + 1;
if (x != t)
{
swap(h[x], h[t]);
down(t);
}
}
int main()
{
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> h[i];
cnt = n;
for (int i = n / 2; i > 0; --i) down(i); //建树，从倒数第二层开始建，然后向上
while (m--)
{
cout << h[1] << ' ';
h[1] = h[cnt--];
down(1);
}
return 0;
}
tip：
up(x)的基础操作：
①循环
void up(int x)
{
while (x / 2 && h[x / 2] > h[x])
{
swap(h[x / 2], h[x]);
x /= 2;
}
}
②递归
void up(int x)
{
if(x / 2 && h[x / 2] > h[u])
{
swap(h[x / 2], h[x]);
up(x / 2);
}
}
down(x)循环版本:
void down(int i) {
while ((i << 1) <= sz) {
int t = i << 1;
if (t + 1 <= sz && h[t] > h[t + 1]) t ++;
if (h[t] >= h[i]) break;
swap(h[t], h[i]);
i = t;
}
}
模拟堆
题目描述：
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x x x；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第 k k k 个插入的数；C k x，修改第 k k k 个插入的数，将其变为 x x x；
现在要进行 n n n 次操作，对于所有第 2 2 2 个操作，输出当前集合的最小值。
输入格式：
第一行包含整数
n
n
n。
接下来
n
n
n 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式：
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围：
1
≤
n
≤
1
0
5
1≤n≤10^5
1≤n≤105
− 1 0 9 ≤ x ≤ 1 0 9 −10^9≤x≤10^9 −109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
难点：
要找到第
k
k
k 个插入的数，因为插入后会进行上下调整，要额外开辟数组，来储存第
k
k
k 个插入的数在堆中的位置。
代码实现：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
// h代表heap（堆），ph（point->heap）可以获得第几个插入的元素现在在堆的那个位置
// hp(heap->point)可以获得在堆的第n个元素存的是第几个插入的元素
int h[N], ph[N], hp[N], cnt;
void heap_swap(int a, int b)
{
// 根据a和b的位置找到它们分别是第几个插入的元素，然后将其（在h数组中的）下标转换
swap(ph[hp[a]], ph[hp[b]]);
// 将两个位置存的是第几号元素转换
swap(hp[a], hp[b]);
// 最后再转换值(这三个语句位置可以换，但是从上到下逐渐变短的话比较美观)
swap(h[a], h[b]);
}
void down(int x)
{
int t = x;
if (2 * x <= cnt && h[2 * x] < h[t]) t = 2 * x;
if (2 * x + 1 <= cnt && h[2 * x + 1] < h[t]) t = 2 * x + 1;
if (t != x)
{
heap_swap(x, t);
down(t);
}
}
void up(int x)
{
while (x / 2 && h[x] < h[x / 2])
{
heap_swap(x, x / 2);
x >>= 1;
}
}
int main()
{
cin.tie(0);
int n, m = 0;
cin >> n;
while (n--)
{
string s;
int k, x;
cin >> s;
if (s == "I")
{
cin >> x;
cnt++;
m++;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
else if (s == "PM") cout << h[1] << endl;
else if (s == "DM")
{
heap_swap(1, cnt);
cnt--;
down(1);
}
else if (s == "D")
{
cin >> k;
k = ph[k];
heap_swap(k, cnt);
cnt--;
up(k);
down(k);
}
else if (s == "C")
{
cin >> k >> x;
k = ph[k];
h[k] = x;
up(k);
down(k);
}
else cout << "error" << endl;
}
return 0;
}
