Priority Queue

A Priority Queue is an abstraction in which every element has a priority. The element with the highest priority is removed first, rather than the earliest one, as in a regular Queue.

Priority Queue vs Regular Queue

Implementation with a Heap

A heap is the most efficient implementation for a Priority Queue.

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.counter = 0  # to break ties

    def enqueue(self, item, priority):
        heapq.heappush(self.heap, (-priority, self.counter, item))
        self.counter += 1

    def dequeue(self):
        if not self.heap:
            raise IndexError("Priority queue is empty")
        priority, _, item = heapq.heappop(self.heap)
        return item, -priority

    def is_empty(self):
        return len(self.heap) == 0

    def peek(self):
        if not self.heap:
            raise IndexError("Priority queue is empty")
        return self.heap[0][2], -self.heap[0][0]

Usage Example

pq = PriorityQueue()
pq.enqueue("Low task", 1)
pq.enqueue("High task", 3)
pq.enqueue("Medium task", 2)

while not pq.is_empty():
    item, priority = pq.dequeue()
    print(f"{item} (priority: {priority})")
# Output:
# High task (priority: 3)
# Medium task (priority: 2)
# Low task (priority: 1)

Time Complexity

Implementation Comparison

Applications

1. Dijkstra's Algorithm: Finding the shortest path.
2. Task Scheduling: An OS picks high-priority processes.
3. Event-Driven Simulation: Events are processed by time.
4. A Search*: Pathfinding with a heuristic.
5. Streaming Median: Two heaps for a running median.

# Dijkstra using a priority queue
import heapq

def dijkstra_simple(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
    return dist

A Priority Queue is an essential tool for graph algorithms. Now let's study the Trie for string search.