二叉堆

根号三 2026年3月18日 73

0 评论

下面是题目

题目一

题目概述

给定一个初始为空的整数数列，需要支持以下三种操作：

1. 插入操作：给定一个整数 $x$，将 $x$ 插入到数列中。
2. 查询操作：输出当前数列中的最小值。
3. 删除操作：删除当前数列中的最小值。若最小值存在多个，仅删除其中一个。

要求按照输入顺序依次处理所有操作，并对每个查询操作输出结果。

题解

这是一道堆的模板题，会使用priority_queue就能做

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	priority_queue<ll,vector<ll>,greater<ll>> pd;
	int n;
	cin >> n;
	while(n--)
	{
		int opt;
		cin >> opt;
		if(opt == 1)
		{
			ll x;
			cin >> x;
			pd.push(x);
		}
		else if(opt == 2)
		{
			int ans = pd.top();
			cout << ans << "\n";
		}
		else{
			pd.pop();
		}
	}
 } 

题目二

题目概述

在一个果园中，已将所有果子按种类划分为 $n$ 堆，第i 堆果子的数量为 $a_i$。每次可选择任意两堆果子合并为一堆，合并后新堆的数量为两堆之和，且该次操作的代价等于两堆果子数量之和。经过 $n-1$ 次合并后最终得到一堆，定义总消耗为所有合并操作代价之和。求一种合并顺序，使总消耗最小，并输出该最小值。

题解

这是一道堆的应用，对于Huffman树问题，可以直接贪心每次合并最小的两个数就可以保证总消耗最小，可以证明。使用小根堆即可。、

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	priority_queue<int,vector<int>,greater<int>> pq;
	for(int i = 0 ; i < n; i++)
	{
		int x;
		cin >> x; 
		pq.emplace(x);
	}
	int ans = 0;
	while(pq.size() != 1)
	{
		int x = pq.top(); pq.pop();
		int y = pq.top(); pq.pop();
		ans += x+y;
		pq.push(x+y);
	}
	cout << ans << endl;
}

题目三、中位数

题目概述

给定一个长度为 N 的非负整数序列 A，依次考虑其前缀子序列。当只取前奇数个元素（即前 $1,3,5,\dots$ 项）时，需要分别求出这些子序列的中位数并输出。中位数定义为将当前子序列排序后处于正中间位置的数。最终输出 $\left\lfloor \frac{N+1}{2} \right\rfloor$ 个结果，每个对应一个奇数长度前缀的中位数。

题解

这道题目需要用两个堆来实现，一大大根堆一个小根堆。然后我们维护一个数mid，每次加入新的数的时候，判断和mid的大小，小于mid的值就push到大根堆，反之push小根堆。这样就可以保证小根堆的top大于mid并且是小根堆中最小的，大根堆也是同理。每2个循环判断一下大根堆和小根堆的数量，如果两边的数量不相等，就把哪一边top取出来并且pop()，将另一边push一个mid，然后mid复制top。这样就可以实现维护mid输出奇数长度的中位数了

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	vector<ll> a(n+5);
	priority_queue<ll,vector<ll>,greater<ll>> p1;
	priority_queue<ll> p2;
	
	for(int i = 0; i < n; i++) cin >> a[i];
	ll mid = a[0];
	cout << mid << endl;
	for(int i = 1; i < n; i++)
	{
		ll temp = a[i];
		if(temp > mid)
		{
			p1.push(temp);
		}
		else p2.push(temp);
		if(i % 2 == 0)
		{
			while(p1.size()!=p2.size())
			{
				if(p1.size() > p2.size())
				{
					int t = p1.top();p1.pop();
					p2.push(mid);
					mid = t; 
				}
				else{
					int t = p2.top();p2.pop();
					p1.push(mid);
					mid = t;
				}
			}
			cout << mid << "\n";
		}
	 } 
}