C++

注意,c++中优先队列的顺序是反的!

#include <queue>

// 用自定义比较函数构造优先队列
priority_queue <Type, vector<Type>, ComparisonType > min_heap;

// 用greater是小顶堆!!pop出来的是最小元素
priority_queue<int, vector<int>, greater<int> >greaterQue;

// 用less是大顶堆!!
priority_queue<int, vector<int>, less<int> >lessQue;

默认是用less,即大顶堆:

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    int value; 
    priority_queue<int>pq;
    pq.push(1); 
    pq.push(2); 
    pq.push(3); 
    while(!pq.empty()) 
    { 
        value = pq.top(); 
        pq.pop(); 
        cout<<value<< " "; 
    } 
    return 0; 
}

// Output : 3 2 1 (default is max heap)

也可以自定义构造函数:

法一:在结构体中重载 ><操作符

struct Stu{
    int age;
    string name;
    Stu(int age1, string name1){
        age = age1;
        name = name1;
    }
    bool operator > (const Stu &s1) const {
        if (s1.age == age)return name > s1.name;
        return age > s1.age;
    }
};

int main(){
    ios::sync_with_stdio(false);
    priority_queue<Stu, vector<Stu>, greater<Stu> >que1;
    que1.push(Stu{11, "yalexin"});
    que1.push(Stu{11, "axin"});
    que1.push(Stu{12, "aaaaa"});
    que1.push(Stu{12, "bbbbb"});
    while(!que1.empty()){
        Stu top = que1.top();
        cout << "age : " << top.age << ", name : " << top.name << endl;
        que1.pop(); 
    }
    return 0;
}

/*
age : 11, name : axin
age : 11, name : yalexin
age : 12, name : aaaaa
age : 12, name : bbbbb
*/

法二:额外定义一个结构体,重载 ()操作符

struct Stu{
    int age;
    string name;
    Stu(int age1, string name1){
        age = age1;
        name = name1;
    }
};
struct MyCmp{
    bool operator()(const Stu &a, const Stu &b){
        if (a.age == b.age) return a.name > b.name;
        return a.age > b.age;
    } 
};
int main(){
    ios::sync_with_stdio(false);
    priority_queue<Stu, vector<Stu>, MyCmp >que1;
    que1.push(Stu{11, "yalexin"});
    que1.push(Stu{11, "axin"});
    que1.push(Stu{12, "aaaaa"});
    que1.push(Stu{12, "bbbbb"});
    while(!que1.empty()){
        Stu top = que1.top();
        cout << "age : " << top.age << ", name : " << top.name << endl;
        que1.pop(); 
    }
    return 0;
}

/* 结果一样
age : 11, name : axin
age : 11, name : yalexin
age : 12, name : aaaaa
age : 12, name : bbbbb
*/

python

default is min heap!

you can use negative sign to convert the min heap to max heap!

heapq.heappush(mylist, ele)     # time O(log k), where k is the heap size 
heapq.heappop(mylist)           # time O(log k) 
heapq.heapify(mylist)           # heapify time is O(n)