堆/题解 P3378 【【模板】堆】

概念：

堆就是一颗二叉树，满足父亲节点总是比儿子节点大（小）。因此，堆也分为大根堆和小根堆，大根堆就是父亲节点比儿子节点大，小根堆正好相反。注意加粗的地方，是每一个节点哦！！！！！

还是直接看例题吧，这样讲起来更加生动。

解析：

这道题明显就是一个小根堆，那，怎么实现呢？热爱数组的我选择了数组实现明明就是指针不会。

操作1：添加一个数字

这里需要用到两个函数，一个insert函数，用来插入，一个ufix函数，用来更新。

void ufix(int i){

	if(i <= 1) return;	//如果都到根了，退出

	if(h[i] < h[i / 2]){	//向上比较

		swap(h[i] , h[i / 2]);

		ufix(i / 2);

	}

}

void insert(int x){

	h[++tot] = x;	//在末尾加上这个数，然后进行更新

	ufix(tot);	//对这个点进行更新

}

操作2：输出最小的数字（也就是堆顶）

直接输出堆顶就行了qwq。

if(x == 2) cout << h[1] << endl;

操作3：删除最小的数字（也就是堆顶）

这里也需要两个函数，一个delet函数，用来删除，一个dfix函数，用来更新。

void dfix(int i){

	if(h[i] == 0x3fffffff) return;	//如果已经越界了，就直接退出

	int k;

	if(h[i * 2] < h[i * 2 + 1]) k = i * 2;	//比较左右儿子谁更优

	else k = i * 2 + 1;

	if(h[i] > h[k]){	//看自己是否需要更新

		swap(h[i] , h[k]);

		dfix(k);

	}

}

void delet(){

	swap(h[1] , h[tot]);

	h[tot--] = 0x3fffffff;	//删除

	dfix(1);

}

完整代码

#include <bits/stdc++.h>

using namespace std;

int n , tot = 0;

int h[1000010];

void ufix(int i){

	if(i <= 1) return;

	if(h[i] < h[i / 2]){

		swap(h[i] , h[i / 2]);

		ufix(i / 2);

	}

}

void dfix(int i){

	if(h[i] == 0x3fffffff) return;

	int k;

	if(h[i * 2] < h[i * 2 + 1]) k = i * 2;

	else k = i * 2 + 1;

	if(h[i] > h[k]){

		swap(h[i] , h[k]);

		dfix(k);

	}

}

void insert(int x){

	h[++tot] = x;

	ufix(tot);

}

void delet(){

	swap(h[1] , h[tot]);

	h[tot--] = 0x3fffffff;

	dfix(1);

}

int main(){

	cin >> n;

	fill(h + 1 , h + 1000010 + 1 , 0x3fffffff);

	while(n--){

		int x;

		cin >> x;

		if(x == 1){

			cin >> x;

			insert(x);

		}else if(x == 2) cout << h[1] << endl;

		else delet();

	}

	return 0;

}

其实优先队列可以直接A的（其内部就是堆实现嘛），但是自己手写一遍可以加深理解哦。

巴特西

堆/题解 P3378 【【模板】堆】

概念：

解析：

最新文章

热门文章