build-priority-queue

build-priority-queue

When to Use

• A* or Dijkstra pathfinding
• Event-driven simulation
• Task scheduling by priority
• Any "process best/smallest first" pattern
• Merging sorted streams
• Top-K problems

When NOT to Use

• FIFO order (use deque)
• LIFO order (use list as stack)
• Need to update priorities frequently (use indexed heap)

The Pattern

Use heapq for O(log n) push/pop of minimum element.

import heapq

# Basic usage
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappop(heap)  # Returns 1 (minimum)

# With tuples for priority ordering
tasks = []
heapq.heappush(tasks, (priority, task_id, task_data))
_, _, task = heapq.heappop(tasks)

# heapify existing list
data = [3, 1, 4, 1, 5]
heapq.heapify(data)  # In-place, O(n)

Example (from pytudes AdventUtils.ipynb)

import heapq

class PriorityQueue:
    """A queue where the item with minimum key is always popped first."""

    def __init__(self, items=(), key=lambda x: x):
        self.key = key
        self.items = []  # Heap of (score, item) pairs
        for item in items:
            self.add(item)

    def add(self, item):
        """Add item to the queue."""
        pair = (self.key(item), item)
        heapq.heappush(self.items, pair)

    def pop(self):
        """Pop and return the item with minimum key."""
        return heapq.heappop(self.items)[1]

    def top(self):
        """Peek at minimum item without removing."""
        return self.items[0][1]

    def __len__(self):
        return len(self.items)

# Usage in A* search
def astar_search(problem, h):
    frontier = PriorityQueue([Node(problem.initial)],
                             key=lambda n: n.path_cost + h(n))

    while frontier:
        node = frontier.pop()
        if problem.is_goal(node.state):
            return node
        for child in expand(problem, node):
            frontier.add(child)

    return None

Key Principles

1. Heap property: Parent <= children (for min-heap)
2. Tuple ordering: (priority, tiebreaker, data) for stable ordering
3. heapify is O(n): Faster than n pushes for initial data
4. No decrease-key: Python heapq doesn't support it; add duplicates instead
5. Wrap for clarity: PriorityQueue class hides heap details