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 AssemblyAI

Automatic Speech Recognition with AssemblyAI

Experience near-human accuracy, low-latency performance, and advanced Speech AI capabilities with AssemblyAI's Speech-to-Text API. Sign up today and get $50 in API credit. No credit card required.

Try the API

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 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