題目連結：【模板】堆

【模板】堆

題目描述

給定一個數列，初始為空，請支援下面三種操作：

1. 給定一個整數 \(x\)，請將 \(x\) 加入到數列中。
2. 輸出數列中最小的數。
3. 刪除數列中最小的數（如果有多個數最小，只刪除 \(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 \leq 15\)。
• 對於 \(70\%\) 的資料，保證 \(n \leq 10^4\)。
• 對於 \(100\%\) 的資料，保證 \(1 \leq n \leq 10^6\)，\(1 \leq x \lt 2^{31}\)，\(op \in \{1, 2, 3\}\)。

這道題考察的是小頂堆的使用

方法一：暴力求解(程式碼這裡就不寫了)

方法二：手寫堆

#include<bits/stdc++.h>
using namespace std;
long long n,heap[10000000],t=0;
void sup(int i){
	int flag=0;
	if(i==1)return ;
	while(i!=1&&flag==0){
		if(heap[i]<heap[i/2])
			swap(heap[i],heap[i/2]);
		else
			flag=1;
		i/=2;
	}
}
void sdown(int i){
	int l,f=0;
	while(i*2<=t&&f==0){
		if(heap[i]>heap[i*2])
			l=i*2;
		else
			l=i;
		if(i*2+1<=t){
			if(heap[l]>heap[i*2+1])
				l=2*i+1;
		} 
		if(l!=i){
			swap(heap[l],heap[i]);
			i=l;
		}else
			f=1;
	}
}
void del(int i){
	heap[i]=heap[t];
	t--;
	sdown(i);
}
int main(){
	cin>>n;
	int op;
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op==1){
			cin>>heap[++t];
			sup(t);
		}
		if(op==2){
			cout<<heap[1]<<endl;
		}
		if(op==3){
			del(1);
		}
	}
	return 0;
}

方法三：STL優先佇列

#include<bits/stdc++.h>
using namespace std;
int n,x;
int main(){
	priority_queue <int,vector<int>,greater<int> > q;
	cin>>n;
	int op;
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op==1){
			cin>>x;
			q.push(x);
		}
		if(op==2){
			cout<<q.top()<<endl;
		}
		if(op==3){
			q.pop();
		}
	}
	return 0;
}