priority_queue兑现最小堆和最大堆

priority_queue实现最小堆和最大堆

注意：

即使最小堆中元素为基本类型（如，int），也不能直接声明

priority_queue<int>qmax;

因为，priority_queue<int>默认按照 < 运算符 的定义比较堆中的元素，并且默认是堆的根部为 <运算符 比较得到的最大元素 （即默认最大堆实现）。

 

为了简化实现，只要记住统一将 堆中元素设置为自定义的struct 即可!

 

#include<iostream>
#include<queue>
using namespace std;
struct MAX
{
    int x;
}t;
struct MIN
{
    int x;
}s;
bool operator<(const MAX &a,const MAX &b)
{
    return a.x<b.x;
}//大根堆
bool operator<(const MIN &a,const MIN &b)
{
    return a.x>b.x;
}//小根堆
priority_queue<MAX>qmax;
priority_queue<MIN>qmin;
int a,n,i;
int main()
{
    cout<<"输入n"<<endl;
    cin>>n;
    cout<<"输入n个数"<<endl;
    for(i=1;i<=n;i++)
    {
        cin>>a;
        t.x=a;
        qmax.push(t);
        s.x=a;
        qmin.push(s);
    }
    while(!qmax.empty())
    {
        a=qmax.top().x;
        cout<<a<<" ";
        qmax.pop();
    }
    cout<<endl;
    while(!qmin.empty())
    {
        a=qmin.top().x;
        cout<<a<<" ";
        qmin.pop();
    }
    cout<<endl;
    system("pause");
    return 0;
}