Abstract Data Type

Priority Queue (PQ)

A priority queue is just a list of Queues sorted by priority. Depending on how the priority queue is implemented, you have different time complexities.

You can implement it using Array, Linked List, Vector, but the most natural choice is a Heap (Data Structure).

Links

• https://www.hackerearth.com/practice/notes/heaps-and-priority-queues/

C++

By Default, the C++ priority queue is a Max Heap and uses C++ Vector (see reference).

priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout << q.top() << "\n"; // 7
q.pop();
cout << q.top() << "\n"; // 5
q.pop();
q.push(6);
cout << q.top() << "\n"; // 6
q.pop();

If we want to create a priority queue that supports finding and removing the smallest element, we can do it as follows:

priority_queue<int, vector<int>, greater<int>> q;

Priority queues allow for duplicate values to be stored.

You can also implement a Priority Queue using a Heap.

For a priority queue of key-pairs, you can us the following:

# Max heap
priority_queue<pair<int, int>> pq;
 
 
# Min Heap
typedef pair<int, int> pi;
priority_queue<pi, vector<pi>, greater<pi> > pq;

NOTE: This is still different from an Ordered Map.

Why do we implement a priority queue with a heap?

We get insertion time and deletion time on average of $O(1)$, unlike a BST which is $O(\log n)$. So then why aren’t heaps used more often? Well, like in an Ordered Map, we need the keys to be ordered, and access every key in an ordered fashion.

Priority queues allow for duplicate values to be stored.

Python

Implemented as a min priority-queue

import heapq
 
heap = []
heapq.heappush(heap, 10)  # heap = [10]
heapq.heappush(heap, 5)   # heap = [5, 10]
heapq.heappush(heap, 15)  # heap = [5, 10, 15]
heapq.heappush(heap, 1)   # heap = [1, 5, 15, 10]
 
# Pop elements from the heap using heapq.heappop()
smallest = heapq.heappop(heap)  # heap = [5, 10, 15]
print(smallest) # 1
 

You can also use heapify

import heapq
 
# Create an unordered list
unordered_list = [12, 3, 5, 7, 19, 1]
 
# Convert the list into a heap using heapq.heapify()
heapq.heapify(unordered_list)  # Now unordered_list becomes a heap
 
# Display the heapified list
print("Heapified list:", unordered_list)  # Output will be a valid heap: [1, 3, 5, 7, 19, 12]
 

Related

• Heap