二叉堆

前言

平常都用priority_queue,今天来手搓一下

定义

二叉堆肯定是个完全二叉树(父节点有左右两节点最底层除外,最底层保证从左到右的连续就可)

用数组a来存二叉树吧,一共n个节点, a[1]是根节点,i节点的左节点是2i,右节点是2i+1,如果大于了n就没有子节点.同样反过来i的父节点就是i/2

代码

实现一个最小堆吧.

https://www.luogu.com.cn/problem/P3378洛谷的堆模板

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
int a[N];
int len = 0;//记现有节点数的 

void push(int x){//上浮(提高优先级的) 添加的优先级最低 
	a[++len] = x;
	int i = len;
	while(i > 1 && a[i] < a[i/2]){ //子比父,父不如子啊 
		swap(a[i], a[i/2]); //老登,辈分该改了
		i/=2; //看看爷爷 
	} 
} ;

void pop(){ //下沉(降低优先级的) 删除的那个优先级最高 
	a[1] = a[len--]; //根节点直接换成叶子节点(因为叶子无牵无挂)
	int i = 1;
	while(i * 2 <= len){//父比子(至少有左子) 
		int sonL = i * 2;//左子 
		int sonR = i * 2 + 1;//右子 
		if(a[i] < a[sonL] || a[i] < a[sonR]){
			if(a[sonL] < a[sonR] || sonR >= len) {//左子好或者右子死掉了
				swap(a[i], a[sonL]); 
				i = sonL;
			}
			else {//右子好 
				swap(a[i], a[sonR]);
				i = sonR;
			}
		}
		else break; //父强,不用看了 
	} 
};

//懒狗,不想封个类了,就用一次 
int main(){
	int n;
	cin>>n;
	while(n--){
		int jud;
		cin>>jud;
		if(jud == 1) {
			int x;
			cin>>x;
			push(x); 
		}
		else if(jud == 2) cout<<a[1]<<endl;
		else pop(); 
	}
	return 0;
}