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

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay