百练 / 2017计算机学科夏令营上机考试: G（最小堆）
发布时间
阅读量：
阅读量
题目来源：http://bailian.openjudge.cn/practice/4078/
4078:实现堆结构
总时间限制: 1000ms 内存限制: 65536kB
描述
定义一个数组，初始化为空。在数组上执行两种操作：
1、增添1个元素，把1个新的元素放入数组。
2、输出并删除数组中最小的数。
使用堆结构实现上述功能的高效算法。
输入
读取一个整数n。
在每次操作中首先读取一个整数type。
当type等于1时：
执行插入操作，并输入一个整数u。
当type等于2时：
执行删除操作，并从数组中删除最小的元素。
满足条件1<=n<=100000。
输出
每次删除操作输出被删除的数字。
样例输入
4
1 5
1 1
1 7
2
样例输出
1
提示
在每组测试数据中采用时间复杂度为O(n\log n)的算法才有可能通过本次任务；否则程序将因超出时间限制而无法完成任务。为了实现本题的目标，请考虑采用基于最小堆的数据结构来构造算法框架。
-----------------------------------------------------
解题思路
最小堆，用priority_queue< int, vector
需要的头文件
#include<queue>
#include<vector>
#include<functional> // std::greater建堆
priority_queue< int, vector<int>, greater<int> > heap; // 最小堆：用std::greater构建优先队列元素入堆
heap.push(openum);取堆顶元素
cout << heap.top() << endl;
堆顶元素出堆
heap.pop();-----------------------------------------------------
代码
#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
ifstream fin("xly2017GG.txt");
int n, j, opecode, openum;
priority_queue< int, vector<int>, greater<int> > heap; // 最小堆：用std::greater构建优先队列
fin >> n;
for (j=0; j<n; j++)
{
fin >> opecode;
if (opecode == 1)
{
fin >> openum;
heap.push(openum);
}
else if(opecode == 2)
{
cout << heap.top() << endl;
heap.pop();
}
}
fin.close();
#endif
#ifdef ONLINE_JUDGE
int n, j, opecode, openum;
priority_queue< int, vector<int>, greater<int> > heap; // 最小堆：用std::greater构建优先队列
cin >> n;
for (j=0; j<n; j++)
{
cin >> opecode;
if (opecode == 1)
{
cin >> openum;
heap.push(openum);
}
else if(opecode == 2)
{
cout << heap.top() << endl;
heap.pop();
}
}
#endif
}全部评论 (0)
还没有任何评论哟~