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
题目描述
给定一个数列，初始为空，请支持下面三种操作：
- 给定一个整数 x，请将 x 加入到数列中。
- 输出数列中最小的数。
- 删除数列中最小的数（如果有多个数最小，只删除 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; }
