什么是STL

以下内容摘自这儿。

STL（Standard Template Library，标准模板库）是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。

堆

堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或 大根堆，根节点最小的堆叫做最小堆或 小根堆。常见的堆有 二叉堆、斐波那契堆等。

大根堆的STL实现

以下代码在 Dev-C++ 5.7.1 中可以编译通过。

声明一个存储 int 类型的大根堆 hep；

priority_queue<int> hep;

声明一个存储 int 类型的小根堆 hep；

priority_queue<int,vector<int>,greator<int> >

注意：`greator<int>` 和右边的 `>` 之间的空格不可略去。

声明堆需要加载头文件

#include<queue>

#include<algorithm>

使用 std 名字空间

using namespace std;

使用STL的缺点，就是常数大。

下面我们以 luoguP3378\text{luoguP3378}luoguP3378 为例，讲解 priority_queue 的调用方法。

题目描述 luoguP3378\text{luoguP3378}luoguP3378

你需要写一个数据结构，支持以下操作：

插入一个数；
询问当前最小的数；
压出当前最小的数。

操作次数 N≤106N\leq 10^6N≤106。

Solution 3378\text{Solution 3378}Solution 3378

Tips：另一种实现小根堆的做法是，存储原数的相反数，查询时再取反输出。详见代码。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#define reg register

using namespace std;

priority_queue<int> hep;

int n;

int s1,s2;

int main(){

	scanf("%d",&n);

	for(reg int i=1;i<=n;++i){

		scanf("%d",&s1);

		switch(s1){

			case 1:

				scanf("%d",&s2);

				hep.push(-s2);	//将新元素的相反数压入堆

				break;

			case 2:

				printf("%d\n",-hep.top());	//取出堆顶元素

				break;

			case 3:

				hep.pop();	//弹出堆顶元素

				break;

			default:

				break;

		}

	}

}

巴特西

基于STL的堆略解

什么是STL

堆

大根堆的STL实现

注意：`greator<int>` 和右边的 `>` 之间的空格不可略去。

使用STL的缺点，就是常数大。

题目描述 luoguP3378\text{luoguP3378}luoguP3378

Solution 3378\text{Solution 3378}Solution 3378

最新文章

热门文章

巴特西

基于STL的堆略解

什么是STL

堆

大根堆的STL实现

注意：greator<int> 和右边的 > 之间的空格不可略去。

使用STL的缺点，就是常数大。

题目描述 luoguP3378\text{luoguP3378}luoguP3378

Solution 3378\text{Solution 3378}Solution 3378

最新文章

热门文章

注意：`greator<int>` 和右边的 `>` 之间的空格不可略去。