堆 标准模板题及基础

STL定义：

最大堆（默认）：

priority_queue<int> heap;

最小堆：

priority_queue<int,vector<int>,greater<int> > heap;

注意！！！虽然是小根堆，但是这里是GREATER!!!

自定义比较器：

struct compare{ bool operater(int a,int b){ return a>b; } }; priority_queue<int,vector<int>,compare> pq;

巨坑！！！

最后一行的堆是小根堆，

而

return a<b;

与排序的顺序相反！

1.模板题：

P3378 【模板】堆

提交答案加入题单复制题目

提交200.08k

通过86.76k

时间限制1.00s

内存限制512.00MB

题目编号P3378

题目描述

给定一个数列，初始为空，请支持下面三种操作：

1. 给定一个整数 x，请将 x 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 1 个）。

输入格式

第一行是一个整数，表示操作的次数 n。
接下来 n 行，每行表示一次操作。每行首先有一个整数 op 表示操作类型。

• 若 op=1，则后面有一个整数 x，表示要将 x 加入数列。
• 若 op=2，则表示要求输出数列中的最小数。
• 若 op=3，则表示删除数列中的最小数。如果有多个数最小，只删除 1 个。

输出格式

对于每个操作 2，输出一行一个整数表示答案。

输入输出样例

输入 #1复制

5 1 2 1 5 2 3 2

输出 #1复制

2 5

说明/提示

【数据规模与约定】

• 对于 30% 的数据，保证 n≤15。
• 对于 70% 的数据，保证 n≤104。
• 对于 100% 的数据，保证 1≤n≤106，1≤x<231，op∈{1,2,3}。

  #include <bits/stdc++.h> using namespace std; int heap[1000005]; int pos=1; void push(int x) { heap[pos]=x; int kid=pos; int dad=kid/2; while (dad>=1 and heap[kid]<heap[dad]) { swap(heap[kid],heap[dad]); kid=dad; dad=kid/2; } pos++; } void down(int n) { int self=n; while(true) { int left=2*self; int right=2*self+1; int smallest=self; if(left<pos and heap[left]<heap[smallest]) { smallest=left; } if(right<pos and heap[right]<heap[smallest]) { smallest=right; } if(smallest!=self) { swap(heap[self],heap[smallest]); self=smallest; }else{ break; } } } void del() { if (pos<=1) return; swap(heap[1],heap[pos-1]); pos--; down(1); } int main() { int n; cin>>n; while(n--) { int op; cin>>op; switch (op) { case 1: { int x; cin>>x; push(x); break; } case 2:{ if(pos>1) { cout<<heap[1]<<endl; } break; } case 3:{ del(); break; } } } return 0; }