本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我会认真改正的。同时也希望文章能够让你有所收获,与君共勉!
昨天被并查集折磨了一天,今天终于可以放松点了。那么今天就主要来学习堆的操作。
这里的堆主要为大顶堆和小顶堆,他们都是以完全二叉树作为数据结构的(完全二叉树不清楚的可以自己去百度下),而完全二叉树一般用数组模拟。接下来谈谈堆能干什么,我们知道每个父节点比子节点的值要大的堆是大顶堆,那么最大值也就是堆顶喽,小顶堆同理,最小值也是堆顶,有了这样的数据结构我们就能以\(O(1)\)的时间复杂度获得最大值和最小值,而堆的主要操作分别是插入一个元素,删除一个元素,修改一个元素,获得集合中最小的元素。具体的就在下面讲吧。
模拟堆
维护一个集合,初始时集合为空,支持如下几种操作:
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
算法原理
初始化
刚刚我们知道堆是用数组实现的完全二叉树h[N]
,除此之外要想实现堆操作,还需要定义cnt
始终指向堆中最后一个结点(其实这时的cnt
就是这个元素在堆中的下标)和进来的顺序m
,以及表示存储x是第几个进来的数组hp[N]
和存储第m
个进来的数在堆h[N]
中所对应的下标ph[N]
。(这里m
和cnt
在数组都是从1开始,这样初始化m=cnt=0
时就要先++m,++cnt
)。
差点忘了,建立一个堆就是不断下沉元素的过程。
插入一个元素
在堆中我们插入一个元素是给h[cnt] = x
,同时需要记录这个元素是第几个进来的hp[cnt] = m
以及这时进来的元素在堆中存储的下标也要被存储起来ph[m] = cnt
,并且将这个元素上浮down(k)
(因为是存储在堆最后的位置的)来寻找这个元素应该在堆中存储的位置。
cin >> x;
++cnt,++m;
h[cnt] = x;
hp[cnt] = m,ph[m] = cnt;
up(cnt);
删除任意一个元素
众所周知,数组删除可以用覆盖来代替,那么如果我们需要删除第k个数,我们通常会用最后一个数覆盖他(方便),这里的覆盖就是堆交换heap_swap(k,cnt)
,然后调整最后一个数到它应该到的位置,即上浮下沉一遍up(k).down(k)
,从树的角度就是把最后一个数看看是往上走,还是往下走。
修改结点值
修改跟删除一样h[k] = x
,删除完之后就调整修改后节点的位置,即上浮下沉一遍。
获得集合里的最值
这个更简单,下标为1的结点就是堆顶h[1]
,就是最大值或最小值,直接输出就行。
这些操作中就有堆的核心操作,上浮和下沉,还有堆交换(比较难理解),接下来就来介绍这些核心操作,以小顶堆为例。
上浮(参数是元素在堆中的下标)
由小顶堆的性质我们可以知道,如果一个节点比他的父节点小,那么我们就需要把他上浮,那么怎么上浮呢,我们可以一直比较该节点与其父节点的大小,如果比它小,就进行堆交换,那么什么时候停止呢?当该节点比父节点要大时就满足小顶堆性质了,可以停止循环,还有一种情况就是该结点就是最小值,那么它就会到这个堆的堆顶去,即当前节点的下标为1时也要停止循环。
void up(int x){
while(x/2 || h[x/2] > h[x]){
heap_swap(x,x/2);
x >>= 1;
}
}
下沉(参数是元素在堆中的下标)
同理,如果一个结点值比他的子节点要大,他就要下沉,由于子节点有两个-左右儿子,因此需要比较与子节点的大小,如果满足条件就先堆交换在下沉,不断下沉直至到达合适的位置,当然要是不满足条件就不必下沉。
void down(int x){
int t = x;
if(2*x <= cnt && h[2*x] < h[t]) t=x*2;
if(2*x+1 <= cnt && h[2*x+1] < h[x]) t=2*x+1;
if(x!=t){
heap_swap(x,t);
down(t);
}
}
堆交换(参数是元素在堆中的下标)
对于x,y两个数,首先要知道他们当前在堆中的下标a
,b
然后才能heap_swap(a,b)
,那么怎么交换这两个数在堆中的位置呢。
首先就得要知道他们什么时候进来的hp[a]
,hp[b]
,交换这个顺序在堆中存储的下标swap(ph[hp[a]],ph[hp[b]])
。
然后交换他们进来的先后顺序swap(hp[a],hp[b])
。
最后在交换在堆中的值swap(h[a],h[b])
。
void heap_swap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int h[N]; // 存储堆的值
int hp[N]; // 下标为a所对应的数--表示一种顺序
int ph[N]; // 第k个数所对应的下标a--指针
int cnt,m; // 最后一个数
// 交换三组:
// 1.对这两个数的下标所对应的顺序值,第几个值(顺序值)在堆中所对应的下标进行交换
// 2.先交换存储在ph中某两个相对(插入的顺序)的数所指向堆中的下标
// 3.最后交换a,b这两个位置的值
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 x){
int t = x;
if(x * 2 <= cnt && h[2*x] < h[t]) t = 2*x;
if(x * 2 + 1 <= cnt && h[2*x + 1] < h[t]) t = 2*x+1;
if(x != t){
heap_swap(x,t); // 交换x,t,与堆排序的不同,这里使用的是heap_swap,只需要提供下标,再函数内部堆下标所指向的数及进行排序
down(t);
}
}
void up(int x){
while(x / 2 && h[x/2] > h[x]){ // x/2
heap_swap(x,x/2);
x >>= 1;
}
}
int main()
{
int n;
cin >> n;
while(n--){
string op;
int x,k;
cin >> op;
if(op == "I"){
cin >> x;
++cnt,++m;
h[cnt] = x; // cnt所对应存储在堆h中的值
ph[m] = cnt,hp[cnt] = m; // cnt是下标,m是第几个数,都从1开始
up(cnt); // 插入位置的元素上浮
}
else if(op == "D"){ // 删除:删除第k个数,那就拿最后一个数覆盖他,然后对这个数调整
cin >> k;
k = ph[k];
heap_swap(k,cnt);
cnt--;
up(k); // 不管交换后最后一个的值是大还是小,都先上浮或下浮一遍.
down(k);
}
else if(op == "C"){
cin >> k >> x;
k = ph[k]; // 找到第k数所对应的下标
h[k] = x; // 将对应的位置修改值
up(k); // 调整修改后的数的位置
down(k);
}
else if(op == "PM"){
cout << h[1] << endl;
continue;
}
else{ // "DM"删除最小值
heap_swap(1,cnt);
cnt--;
down(1); // 只能向下调整
}
}
return 0;
}
标签:11,cnt,下标,int,hp,swap,2022,ph,Acwing
From: https://www.cnblogs.com/WangChe/p/16895805.html