考研复试系列——第二节最大堆&最小堆

本文链接：https://blog.csdn.net/cassiePython/article/details/57405329

考研复试系列——第二节最大堆&最小堆

前言

在中科大，上交，浙大的上机题目中，堆的使用频繁出现，在机试时我们不可能从头到尾自己去实现最大堆，最小堆的操作

绕过对堆的实现，我们使用C++ STL中的优先队列来解决堆的相关问题

基础知识

随便举个例子，给定一个n和m ,接下来输入n个数，计算这n个数中前m个最大的数（当然可以用排序来做）

#include<iostream>
#include<queue>
using namespace std;

int main()
{
	//最大堆的使用
	priority_queue<int> que;
	int n,m;
	cin>>n>>m;
	int i;
	for(i=0;i<n;i++)
	{
		int number;
		cin>>number;
		que.push(number);
	}
	for(i=0;i<m;i++)//输出前m个最大的值
	{
		cout<<que.top()<<" ";
		que.pop();
	}
	cout<<endl;
	return 0;
}

如果题目更改一下，要求前m个最小的数呢

#include<iostream>
#include<queue>
using namespace std;

int main()
{
	//最小堆的使用
	priority_queue<int ,vector<int> ,greater<int> > que;
	int n,m;
	cin>>n>>m;
	int i;
	for(i=0;i<n;i++)
	{
		int number;
		cin>>number;
		que.push(number);
	}
	for(i=0;i<m;i++)//输出前m个最小的值
	{
		cout<<que.top()<<" ";
		que.pop();
	}
	cout<<endl;
	return 0;
}

对于结构体的支持

#include <iostream>
#include <queue>
using namespace std;
struct Node
{
	int x, y;
}node;
bool operator<( Node a, Node b)//运算符重载
{
    if(a.x==b.x) return a.y>b.y;
    return a.x>b.x;
}
int main()
{
    priority_queue<Node> que;
    for(int i=0;i<10;i++){
    	node.x=i;
    	node.y=10-i/2;
    	que.push(node);
    }	
    while(!que.empty()){
        cout<<que.top().x <<" "<<que.top().y<<endl;
        que.pop();
    }
    return 0;
}

写法二：

#include <iostream>
#include <queue>
using namespace std;
struct Node
{
	int x, y;
}node;
struct cmp
{
    bool operator()(Node a,Node b)
	{
        if(a.x==b.x) 
			return a.y>b.y;
        return a.x>b.x;
	}
};

int main()
{
    priority_queue<Node,vector<Node>,cmp>q;
    for(int i=0;i<10;i++)
	{
    	node.x=i;
    	node.y=10-i/2;
		q.push(node);	
    }	
    while(!q.empty())
	{
        cout<<q.top().x<<' '<<q.top().y<<endl;
        q.pop();
    }
    return 0;
}

例题

例题一：哈夫曼树

哈夫曼树，第一行输入一个数n，表示叶节点的个数，接下来输入n个weight ，其中 2<= n <= 1000.

输出所有节点的值与权重的乘积之和。

sample：

1 2 2 5 9

sample output：

#include<iostream>
#include<queue>
using namespace std;

int main()
{
	priority_queue<int ,vector<int> ,greater<int> > que;
	int n;
	cin>>n;
	int i;
	for(i=0;i<n;i++)
	{
		int number;
		cin>>number;
		que.push(number);
	}
	int ans = 0;//保存结果
	while(que.size() > 1)
	{
		int one = que.top();//先取两个最小值
		que.pop();
		int two = que.top();
		que.pop();
		ans += one + two;
		que.push(one + two);//将两个最小值的和加入堆
	}
	cout<<"结果是:"<<ans<<endl;
	return 0;
}

例题二：

序列A 中有 N 个元素，序列 B 中也有 N 个元素，依次将序列 B 中的元素移进序列 A ，对于每次移进元素，首先在一行输出序列 A 中的最小值，

然后在 A 在加入该元素，接着在序列 B 中删除该元素，接着在序列 A 中删除刚才输出的最小值。

sample input：

3 9 6

5 2 10

sample output：

#include<iostream>
#include<queue>
using namespace std;

int main()
{
	/*
	最小堆也可以这样定义
	struct cmp    
	{    
		bool operator ()(const int &i,const int &j)    
		{    
			return i>j;    
		}    
	}; 
	priority_queue<int ,vector<int> ,cmp> que;
	*/
	priority_queue<int ,vector<int> ,greater<int> > que;//最小堆
	int b[1000];
	int n;
	cin>>n;
	int i;
	for(i=0;i<n;i++)//输入a
	{
		int a;
		cin>>a;
		que.push(a);
	}
	for(i=0;i<n;i++)//输入b
		cin>>b[i];
	for(i=0;i<n;i++)
	{
		cout<<que.top()<<endl;
		que.pop();
		que.push(b[i]);
	}
	return 0;
}