Priority Queue in Data Structure — Implementation, Types & More

A Priority Queue is an abstract data type in which each element has an associated priority. Elements are served not in the order they were added, but based on their priority — the highest (or lowest) priority element is served first.

Types

• Max Priority Queue: the element with the highest priority is served first.
• Min Priority Queue: the element with the lowest priority is served first.

Implementation Using a Binary Heap

Priority queues are most commonly implemented using a binary heap, which allows insertion and extraction of the highest/lowest priority element in O(log n) time.

import heapq

# Min-priority queue (Python's heapq is a min-heap by default)
pq = []
heapq.heappush(pq, (2, "task B"))
heapq.heappush(pq, (1, "task A"))
heapq.heappush(pq, (3, "task C"))

while pq:
    priority, task = heapq.heappop(pq)
    print(priority, task)   # prints in order 1, 2, 3

Complexity

Applications

• Dijkstra's and Prim's algorithms for graph traversal.
• Task scheduling based on priority/deadline.
• Huffman coding for data compression.