Introduction

A priority queue is an abstract data type that operates much like a regular queue, except each element has an associated “priority”. Instead of strictly First-In-First-Out, the element with the highest priority is served before others. Depending on the implementation, this can mean either the largest value first (max-heap behavior) or the smallest value first (min-heap behavior). In practice, priority queues are often implemented with heaps (binary heaps) because heaps efficiently support the required operations.

Coding interview problems commonly use priority queues (heaps) when you need quick access to the smallest or largest elements in a collection. Heaps are a go-to solution in scenarios like:

• Top K or k-th extremes: e.g. “find the k largest elements” or “k-th smallest element”.
• Streaming minima/maxima: e.g. “running median” uses two heaps.
• Ordering by priority: e.g. scheduling tasks or events by priority.
• Merging or sorting problems: e.g. merge k sorted lists.

Core Idea / Mental Model

At its core, a heap is a complete binary tree that maintains a partial order called the heap property: each parent node is either ≤ its children (min-heap) or ≥ its children (max-heap). This guarantees that the root of the tree is always the global minimum (for a min-heap) or maximum (for a max-heap). Whenever you insert a new element or remove the root, the tree re-adjusts itself to restore this heap property.

Mental model: Imagine a priority queue like a VIP line. People have different priority statuses, and the person with the highest priority is always at the front. If that person leaves, the next highest priority person moves up. In a min-heap, think of a to-do list where the task with the smallest deadline is tackled first.

Heaps are typically stored in an array for efficiency. For a 0-indexed array arr, children of arr[i] are at 2*i + 1 and 2*i + 2, and the parent is at (i-1)//2. This allows efficient "bubble up" (sift-up) and "bubble down" (sift-down) operations.

Base Template (Using Python’s `heapq`)

In Python, the heapq module provides a min-heap. To simulate a max-heap, insert negative values or use a custom comparator.

import heapq

# Min-Heap example
min_heap = []
heapq.heappush(min_heap, 5) # [5]
heapq.heappush(min_heap, 2) # [2, 5]
heapq.heappush(min_heap, 8) # [2, 5, 8]
# print(min_heap[0])      # Peeks at 2
smallest = heapq.heappop(min_heap) # smallest = 2, min_heap = [5, 8]

# Max-Heap example (by inverting values)
max_heap = []
heapq.heappush(max_heap, -5) # Represents 5. Heap: [-5]
heapq.heappush(max_heap, -2) # Represents 2. Heap: [-5, -2]
heapq.heappush(max_heap, -8) # Represents 8. Heap: [-8, -2, -5]
largest = -heapq.heappop(max_heap) # largest = 8, max_heap = [-5, -2]

# Heapify a list (in-place, O(n) time)
data = [5, 2, 8, 1, 9]
heapq.heapify(data) # data becomes a min-heap, e.g., [1, 2, 8, 5, 9]

heappush adds an element and bubbles it up. heappop removes the root and bubbles down the last element. heapify converts a list to a heap in O(n) time.

Note on Tuples: For custom objects or tuples like (priority, item), if priorities are equal, Python compares the next elements. If non-comparable, include a unique sequence number as a tie-breaker: (priority, sequence_num, item).

Interactive Animation (Min-Heap Operations)

The animation below visualizes min-heap operations: push (insert) and pop (remove min). Observe how the heap structure (both as a tree and an array) is maintained through sift-up and sift-down operations.

Time & Space Complexity (Binary Heap)

• Insertion (heappush): O(log n)
• Removal (heappop min/max): O(log n)
• Peek (find min/max): O(1)
• Build Heap (heapify from list): O(n)

Space Complexity: O(n) to store heap elements. Operations are typically in-place or use minimal auxiliary space (O(log n) for recursion if implemented that way, but Python's `heapq` is iterative).

Common Pitfalls

• Off-by-one Index Errors: When manually implementing heap parent/child index calculations.
• Min-Heap vs Max-Heap Confusion: Python's `heapq` is a min-heap. Negate values for max-heap behavior.
• Incorrect Use of Tuples/Objects: If priorities are equal, Python compares next tuple elements. Use a unique tie-breaker if needed.
• Not Using Heap Operations: Manually modifying the heap list breaks the invariant. Use `heappush`, `heappop`, `heapify`.
• Memory Footprint for Max-Heap Trick: Remember heap stores negated values.
• Recursion in Manual Heapify/Sift: Iterative is often less error-prone. Ensure correct base cases if recursive.