P3378 【模板】堆
【模板】堆
题目描述
给定一个数列，初始为空，请支持下面三种操作：
- 给定一个整数 x，请将 x 加入到数列中。
- 输出数列中最小的数。
- 删除数列中最小的数（如果有多个数最小，只删除 1 个）。
输入格式
第一行是一个整数，表示操作的次数 n。
接下来 n 行，每行表示一次操作。每行首先有一个整数 op 表示操作类型。
- 若 op = 1，则后面有一个整数 x，表示要将 x 加入数列。
- 若 op = 2，则表示要求输出数列中的最小数。
- 若 op = 3，则表示删除数列中的最小数。如果有多个数最小，只删除 1 个。
输出格式
对于每个操作 2，输出一行一个整数表示答案。
样例 #1
样例输入 #1
5
1 2
1 5
2
3
2
样例输出 #1
2
5
提示
【数据规模与约定】
- 对于 30% 的数据，保证 n ≤ 15。
- 对于 70% 的数据，保证 n ≤ 10^4。
- 对于 100% 的数据，保证 1 ≤ n ≤ 10^6，1 ≤ x < 2^31，op ∈{1, 2, 3}。
分析
手写一个堆(原版)
向堆中添加元素的算法(put)如下:(小根堆)
1.在堆尾加入这个元素，并把它标志为当前节点
2.比较当前节点a(下标i)和它父节点b(下标i/2)的大小
{ 1.如果a<b，则swap(a,b)，并把a标志为当前节点，继续.
2.如果a>=b,则退出
} 重复进行n次put操作,便可建一个小根堆
附：下标关系是完全二叉树的性质。
具体来说是读入一个数插入到堆尾，在通过调整以满足堆(这里是小根堆)的性质。
从now=len(堆的大小)开始，判断它于父节点(now>>1/now/2)的大小
若heap[now]<heap[now/2] 则swap(heap[now],heap[now/2])，且now=now/2，继续判断heap[now]于heap[now/2]的大小......
直到now=1或heap[now]>=heap[now/2]为止
代码就是这样
void put(int d)
{
int now,next;
heap[++heap_size]=d;
now=heap_size;
while(now>1)
{
next=now>>1;
if(heap[now]>=heap[next]) return;
swap(heap[now],heap[next]);
now=next;
}
}
从堆中取出并删除这个元素的算法(get)如下:(小根堆)
1.取出堆的根节点的值
2.把堆的最后一个节点(heap_size)放到根上，覆盖掉根,heap_size--.
3.调整调整以满足堆(这里是小根堆)的性质。(put中调整的逆过程)
代码如下
int get()
{
int now,next,res;
res=heap[1];
heap[1]=heap[heap_size--];//注意是heap_size--,而不是--heap_size
now=1;
while(now*2<=heap_size)
{
next=now*2;
if(next<heap_size&&heap[next+1]<heap[next]) next++;
if(heap[now]<=heap[next]) return res;
swap(heap[now],heap[next]);
now=next;
}
return res;
}
本题是3个操作，其实就是把get分成了两个.(取而不删除，删除了不取) 完整代码:
#include"cstdio"
#include"iostream"
#include"cctype"
using namespace std;
int heap_size,n;
int heap[30001];
inline int readint()
{
char c=getchar();
while(!isdigit(c)) c=getchar();
int x=0;
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
int buf[105];
inline void writeint(int i) {
int p = 0;
if(i == 0) p++;
else while(i) {
buf[p++] = i % 10;
i /= 10;
}
for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]);
}
void swap(int &a,int &b)
{
int t=a;a=b;b=t;
}
void put(int d)
{
int now,next;
heap[++heap_size]=d;
now=heap_size;
while(now>1)
{
next=now>>1;
if(heap[now]>=heap[next]) return;
swap(heap[now],heap[next]);
now=next;
}
}
int del()
{
int now,next,res;
res=heap[1];
heap[1]=heap[heap_size--];
now=1;
while(now*2<=heap_size)
{
next=now*2;
if(next<heap_size&&heap[next+1]<heap[next]) next++;
if(heap[now]<=heap[next]) return res;
swap(heap[now],heap[next]);
now=next;
}
}
int get()
{
return heap[1];
}
void work()
{
n=readint();
for(int i=1;i<=n;i++)
{
int x;
x=readint();
if(x==1) {x=readint();put(x);}
else if(x==2) {writeint(get());putchar('\n');}
else del();
}
}
int main()
{
work();
}
STL版堆（push_heap,pop_heap）
#include"cstdio"
#include"iostream"
#include"algorithm"
using namespace std;
int heap_size;
int heap[1000005];
void put(int x)
{
heap[++heap_size]=x;
push_heap(heap+1,heap+1+heap_size,greater<int>());
}
int get()
{
return heap[1];
}
void del()
{
pop_heap(heap+1,heap+1+heap_size,greater<int>());
heap_size--;
}
int main()
{
int n;
scanf("%d",&n);
int x;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(x==1) {scanf("%d",&x);put(x);}
else if(x==2) {printf("%d\n",get());}
else if(x==3) del();
}
}
小根堆其实就是特殊的优先队列(越小的整数优先级越大)
#include"iostream"
#include"algorithm"
#include"queue"
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x==1) {scanf("%d",&x);q.push(x);}
else if(x==2) printf("%d\n",q.top());
else q.pop();
}
}
PS:也可以直接用priority_queue
我只想说写priority_queue<int,vector