Priority Queues

NOTE: This article isn't written in java, therefore the following is for C++

Priority queues are essentially lists whose maximum/minimum item can be accessed in $O(1)$ time. The list itself can be updated in $O(\log n)$, making it ideal for situations where you need to update a list many times while still keeping it "ordered"(you can still access the min/max value really quickly).

Operations

Priority queues have 3 main operations:

• pushing an element into the queue
• popping an element from the queue
• getting the minimum element from the queue

Initialization

Priority queues are implemented using the default lists, so we can initialize the priority queue as the following:

To use a priority queue one first needs to be initialized:

// have to specify the priority queue's data type
priority_queue<int> pq;

pq = []

Push

Push operations put a new element not the priority queue. These take $O(\log n)$ time.

pq.push(value);

heapq.heappush(pq, value)

Pop

Pop operations remove the minimum element in the priority queue. These take $O(\log n)$ time.

pq.pop();

heapq.heappop(pq)

Query/Top

This operation gets the minimum element of the priority queue. These take $O(1)$ time, making them really fast.

This operation gets the maximum element of the priority queue. These take $O(1)$ time, making them really fast.

auto top_value = pq.top();

heapq.heappop(pq)

NOTE: In python, the heappop() function also returns the element that was popped (also equal to pq[0]). This means that

value = pq[0]
heapq.heappop(pq)

and

value = heapq.heappop(pq)

are effectively the same.

All together

The following provides more examples on how it works:

#include <bits/stdc++.h>

using namespace std;

int main(){
    // priority_queue<data type> variable;
    priority_queue<int> pq;

    pq.push(5);
    pq.push(2);
    pq.push(4);

    // pq now has elements 2 4 and 5

    // prints 2
    cout << pq.top() << endl;

    // 2 gets popped, now pq has elements 4 and 5
    pq.pop();

    // pq now has elements 4 and 5
    cout << pq.top() << endl;
}

import heapq

# you can initialize as a normal list
pq = []


heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 4)

# pq now has elements 2 4 and 5

# prints 2 since its the smallest element
print(pq[0])

# 2 gets popped, now pq has elements 4 and 5
heapq.heappop(pq)

# value becomes 4 since that is now the smallest element
value = heapq.heappop(pq)
print(value)

this code outputs

2
4