DEV Community

dinhluanbmt
dinhluanbmt

Posted on

C++, about priority_queue(min max heap)

priority_queue (min/max heap)
Building complexity: O(n) / priority_queue pq(iV.begin(),iV.end());
priority_queue s_pq;
for(auto i: iV) s_pq.push(i) //building time complexity O(n* log n)
pop : O(log n)
push : O(log n)
top : O(1)
default order: max heap( maximum item is on top) - descending order.
min heap (min item on top) - ascending order
priority_queue, std::greater> m_h(iV.begin(),iV.end());
Example code

 vector<int> iV = { 3,5,8,3,6,1,20,4,8,1};
    cout << "==========max heap=============" << endl;
    // building time complexity O(n)
    priority_queue<int> pq(iV.begin(), iV.end());// default order => max heap, descending order
    pq.push(24);//O(log n) time complexity
    while (!pq.empty()) {
        cout << " " << pq.top() << endl; // --> acces the maximum item : O(1)
        pq.pop();// O(log n) time complexity
    }
    //==========
    cout << "==========min heap==============" << endl;
    // min heap, O(n) building time complexity
    priority_queue<int,vector<int>, std::greater<int>> m_h(iV.begin(),iV.end());
    while (!m_h.empty()) {
        cout << " " << m_h.top() << endl;
        m_h.pop();
    }

    priority_queue<int, vector<int>, greater<int>> slow_bh; // O(1) building time
    for (auto i : iV) slow_bh.push(i); // building time O (n* log n) 
Enter fullscreen mode Exit fullscreen mode

Custom data type

struct City {
    int population;
    string name;
    City(int pop = 0, string s = "") {
        population = pop;
        name = s;
    }
    // for max heap
    bool operator< (const City& c) const
    {
        return population < c.population || (population == c.population && name < c.name);
    }
    //for min heap
    bool operator> (const City& c) const {
        return population > c.population || (population == c.population && name > c.name);
    }
    //bool operator== (const City& c) const / for other methods

};
void test_priority_queue() {
    vector<City> cV = { {100,"suwon"},{320,"incheon"},{40,"seoul"},{500,"kwangju"}};
    // max heap
    cout << "========== max heap =============" << endl;
    priority_queue<City> pq(cV.begin(), cV.end());
    while (!pq.empty()) {
        cout << " " << pq.top().population << " " << pq.top().name << endl;
        pq.pop();
    }
    cout << "========== min heap =============" << endl;
    //min heap
    priority_queue<City, vector<City>, std::greater<City>> mc_h(cV.begin(), cV.end());
    while (!mc_h.empty()) {
        cout << " " << mc_h.top().population << " " << mc_h.top().name << endl;
        mc_h.pop();
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)