Priority_queue

Priority_queue (pq) is a powerful data structure that is very suitable for questions requires order or ranks, such as Top K problems. Especially, whenever it requires the k smallest or biggest elements during the a scanning, pq could be very convenient to use.

In C++, 

1. the default order inside a pq is decreasing, or the largest one is the on the top;

2. even though its name having a queue, the built-in function for the top element is pq.top();

3. the elements inside a pq are not strictly sorted, it is more like a heap;

4. when pop out or push in one element, the pq (or heap) can automatically adjust the positions of its elements based on the relative magnitude of the element.

Top K elements:

1. find the k smallest elements in an array

priority_queue<int> pq;
for(auto &a : array) {
    pq.push(a);
    if(pq.size() > k) pq.pop();
}

2. find the k largest elements in an array

priority_queue<int, vector<int>, greater<int>> pq;
for(auto &a : array) {
    pq.push(a);
    if(pq.size() > k) pq.pop();
}

3. find the k largest pairs (based on the first value)

typedef pair<int, int> pr;
priority_queue<pr, vector<pr>, greater<pr>> pq;
for(int i=0; i<array.size(); ++i) {
    pq.push({a*a, i});
    if(pq.size() > k) pq.pop();
}

Question List

Upper Layer