Data Structures & AlgorithmsPriority Queues Revisited

Priority Queues Revisited — Now with Implementation

LevelIntermediate

Duration60 mins

TopicPriority Queues Revisited

2 / 4

Interface: insert, extractMax/extractMin

The Heart of the Priority Queue

A priority queue lives or dies by two operations: insert and extract. Everything else—peek, isEmpty, size—is secondary. These two operations define the structure's fundamental capability: accepting elements with priorities and releasing them in priority order.

In this page, we'll dissect these operations with surgical precision. We'll examine not just what they do, but the exact semantics, invariants, edge cases, and behavioral contracts that any correct implementation must satisfy. This level of rigor might seem excessive for operations that appear simple on the surface—but it's exactly this depth of understanding that separates engineers who use data structures from those who master them.

When you finish this page, you'll be able to reason about priority queue behavior in any context: implementing them from scratch, debugging incorrect behavior, evaluating library implementations, or answering interview questions with confident precision.

Learning Objectives

By the end of this page, you will understand the precise semantics of insert and extract operations, their behavioral invariants, edge cases, error conditions, and how these operations interact. You'll be able to specify a priority queue's behavior as rigorously as any formal specification.

The Insert Operation — Adding to the Collection

Formal Definition:

insert(element: T) → void

The insert operation adds an element to the priority queue. After insertion, the element becomes a candidate for extraction according to its priority relative to other elements in the queue.

Semantic Requirements:

Insert Operation Semantics

•Element Inclusion: After insert(x), the queue contains x. Any subsequent extract operations may return x (if it has the appropriate priority).
•Priority Ordering: The element's priority determines its position in the extraction order. Higher-priority elements will be extracted before lower-priority ones.
•No Immediate Extraction: Insert does not extract anything. The queue size increases by exactly one.
•Duplicate Acceptance: Multiple identical elements may be inserted. Each is a separate entry. If x is inserted twice, two extract operations are needed to remove both.

Pre-conditions and Post-conditions:

Thinking in terms of pre-conditions (what must be true before the operation) and post-conditions (what is guaranteed after) helps us reason precisely:

insert_contract.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Insert Operation Contract
 * 
 * Pre-conditions:
 *   - element is a valid T (satisfies the type constraint)
 *   - If priority is separate from element, priority is comparable
 *   - (Optional) Queue is not at maximum capacity
 * 
 * Post-conditions:
 *   - Queue contains one more element than before
 *   - The inserted element is now in the queue
 *   - All previously existing elements are still in the queue
 *   - The relative ordering of existing elements (by priority) is unchanged
 *   - No element has been extracted
 * 
 * Formally, if we denote:
 *   S  = set of elements before insert
 *   S' = set of elements after insert(x)
 * 
 * Then: S' = S ∪ {x} (multiset union, allowing duplicates)
 *       |S'| = |S| + 1
 */
function insert<T>(element: T): void {
    // Implementation follows...
}

Multiset Semantics

A priority queue is technically a multiset with priority ordering—it can contain duplicate elements. This differs from a set-based priority queue (which might reject duplicates) and has important implications for applications like scheduling where multiple tasks might have identical priorities.

Priority Assignment Strategies

When inserting an element, we must associate it with a priority. There are two fundamental approaches:

Approach 1: Intrinsic Priority

The element is its priority. The element type is naturally comparable, and comparison on elements defines the priority ordering.

// Element IS the priority
pq.insert(5);    // Element 5 with implicit priority 5
pq.insert(3);    // Element 3 with implicit priority 3
pq.extractMin(); // Returns 3 (lower value = higher priority in min-heap)

This works well for numeric types, strings, or any type with natural ordering. It's conceptually simple and avoids the overhead of separate priority tracking.

Approach 2: Extrinsic Priority

The element and priority are separate. Each element carries an associated priority value, and comparison on priorities (not elements) determines order.

priority_strategies.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Approach 2: Element with separate priority
interface PrioritizedElement<T> {
    element: T;
    priority: number;
}
 
// Insert tasks with priorities
pq.insert({ element: "Send email", priority: 3 });
pq.insert({ element: "Update database", priority: 1 });
pq.insert({ element: "Generate report", priority: 2 });
 
pq.extractMin(); // Returns "Update database" (priority 1)
pq.extractMin(); // Returns "Generate report" (priority 2)
pq.extractMin(); // Returns "Send email" (priority 3)
 
// Approach 3: Comparison function (most flexible)
interface Task {
    name: string;
    urgency: number;
    deadline: Date;
}
 
// Custom comparator: lower urgency first, ties broken by earlier deadline
const compareTasks = (a: Task, b: Task): number => {
    if (a.urgency !== b.urgency) {
        return a.urgency - b.urgency;
    }
    return a.deadline.getTime() - b.deadline.getTime();
};
 
const taskQueue = new PriorityQueue<Task>(compareTasks);

Trade-offs Between Approaches:

Priority Assignment Strategy Trade-offs
Strategy	Pros	Cons	Best For
Intrinsic (element = priority)	Simple, no extra storage, natural semantics	Limited to comparable types, can't track original elements separately	Numeric algorithms, sorting helpers
Extrinsic (separate priority)	Any element type, clear separation of concerns	Extra storage, must package element with priority	Task scheduling, event systems
Comparator function	Maximum flexibility, complex ordering rules	Function call overhead, harder to debug	Complex domain objects, multi-criteria ordering

Standard Library Patterns

Most standard library priority queues use the comparator approach. Python's heapq uses element comparison (intrinsic). Java's PriorityQueue accepts a Comparator. C++ priority_queue takes a comparison function. Understanding your library's approach is essential for correct usage.

The Extract Operation — Removing the Extreme

Formal Definition:

extractMin() → T    (for min-priority queue)
extractMax() → T    (for max-priority queue)

The extract operation removes and returns the element with the highest priority (minimum value in a min-heap, maximum value in a max-heap). This is the defining operation that makes a priority queue a priority queue.

Semantic Requirements:

Extract Operation Semantics

•Returns Extreme: The returned element must have priority ≤ (for min-heap) or ≥ (for max-heap) all remaining elements.
•Removes Element: After extraction, the returned element is no longer in the queue. Queue size decreases by exactly one.
•Non-Destructive to Others: All other elements remain in the queue with their priorities unchanged.
•Deterministic on Ties: If multiple elements share the same priority, extraction returns one of them (implementation may or may not be stable).
•Requires Non-Empty: Extracting from an empty queue is an error (undefined behavior, exception, or special return value depending on implementation).

extract_contract.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * ExtractMin Operation Contract
 * 
 * Pre-conditions:
 *   - Queue is not empty (size > 0)
 * 
 * Post-conditions:
 *   - Returns element m such that ∀ x ∈ queue: priority(m) ≤ priority(x)
 *   - m is removed from the queue
 *   - |S'| = |S| - 1  (size decreases by 1)
 *   - ∀ x ∈ S, x ≠ m: x ∈ S'  (other elements unchanged)
 * 
 * Error condition:
 *   - If queue is empty: throw Error / return undefined / assertion failure
 * 
 * Formally, if we denote:
 *   S  = multiset of elements before extract
 *   m  = element with minimum priority in S
 *   S' = multiset after extractMin()
 * 
 * Then: m ∈ S
 *       S' = S - {m}  (multiset difference)
 *       return m
 */
function extractMin<T>(): T {
    if (this.isEmpty()) {
        throw new Error("Cannot extract from empty priority queue");
    }
    // Implementation follows...
}

Critical Detail: Stability

What happens when multiple elements have the same priority? Consider:

insert("A", priority=1)
insert("B", priority=1)
insert("C", priority=1)

All three have priority 1. Which is returned by extractMin()?

A stable priority queue preserves insertion order for equal priorities—it returns "A" first, then "B", then "C". A non-stable priority queue may return them in any order.

Most heap implementations are non-stable. The binary heap has no concept of insertion time; it only considers priority. If you need stability, you must engineer it:

stable_priority_queue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Engineering stability: add insertion timestamp as tie-breaker
interface StableElement<T> {
    element: T;
    priority: number;
    insertionOrder: number;  // Ties broken by this
}
 
class StablePriorityQueue<T> {
    private insertCounter = 0;
    
    insert(element: T, priority: number): void {
        this.heap.insert({
            element,
            priority,
            insertionOrder: this.insertCounter++
        });
    }
    
    // Compare: first by priority, then by insertion order
    private compare(a: StableElement<T>, b: StableElement<T>): number {
        if (a.priority !== b.priority) {
            return a.priority - b.priority;
        }
        return a.insertionOrder - b.insertionOrder;  // FIFO for ties
    }
}

Stability Costs

Adding stability requires extra storage (the insertion counter) and slightly more complex comparisons. For most applications, non-stable behavior is acceptable. But for fair scheduling (first-come-first-served among equal priorities), stability matters. Know your requirements before implementing.

The Peek Operation — Non-Destructive Access

Formal Definition:

peekMin() → T    (for min-priority queue)
peekMax() → T    (for max-priority queue)

Peek returns the same element that extract would return, but without removing it from the queue. The queue remains unchanged.

Why Peek Matters:

At first glance, peek might seem like a convenience operation—just extract and re-insert if you don't want to remove it. But this misses crucial use cases:

Peek Use Cases

•Decision Making: Check the highest-priority task to decide if you should process it now or wait. If priority is 10 (low), maybe sleep. If priority is 1 (critical), process immediately.
•Threshold Checks: Process all elements with priority below threshold. Peek to check, extract if it passes, stop when it doesn't.
•Logging/Monitoring: Log what's about to be processed without affecting the queue state.
•Invariant Checking: In debugging, peek to verify the heap property without mutation.
•Algorithm Requirements: Some algorithms (like merging k sorted lists) need to compare heads of multiple queues without extracting.

peek_use_case.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Use case: Process all tasks until we hit a low-priority one
function processUrgentTasks(pq: PriorityQueue<Task>): void {
    const URGENCY_THRESHOLD = 5;
    
    while (!pq.isEmpty()) {
        // Peek to check without extracting
        const nextTask = pq.peekMin();
        
        if (nextTask.priority > URGENCY_THRESHOLD) {
            // Low-priority task: stop processing, save for later
            console.log(`Stopping: remaining tasks below priority ${URGENCY_THRESHOLD}`);
            break;
        }
        
        // High-priority task: extract and process
        const task = pq.extractMin();
        process(task);
    }
}
 
// Without peek, we'd have to extract and conditionally re-insert!
// That's inefficient and error-prone.

Complexity Expectation:

Peek should be O(1). For a heap, the minimum (or maximum) is always at the root, accessible in constant time. There's no searching, no traversal—just return heap[0].

This is a key advantage of heaps: you always know where the extreme element lives.

Relationship Between Peek and Extract

A useful mental model: extractMin() = peekMin() + deleteMin(). Extract is peek followed by removal. This decomposition often helps in implementation—first find the min (trivial), then remove it (the complex part).

Operation Interplay — Invariants Across Operations

Operations don't exist in isolation. A correct priority queue implementation must maintain invariants across operations. Let's formalize these cross-operation invariants.

Invariant 1: Size Consistency

size_after_insert = size_before_insert + 1
size_after_extract = size_before_extract - 1
size_after_peek = size_before_peek (unchanged)

Invariant 2: Peek-Extract Consistency

Let x = peekMin()
Let y = extractMin()
Then: x == y (same element returned)

Whatever peek returns, extract must return the same element (assuming no intervening operations).

Invariant 3: Extremal Property

After any sequence of operations:

∀ x ∈ queue: priority(peekMin()) ≤ priority(x)

The element returned by peek always has the minimum priority among all elements.

Invariant 4: Extract Ordering

If you extract all elements from a priority queue, they come out in sorted order (by priority).

const results: number[] = [];
while (!pq.isEmpty()) {
    results.push(pq.extractMin());
}
// results is sorted in ascending order (for min-heap)

invariant_testing.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Testing priority queue invariants
function verifyPriorityQueueInvariants<T>(
    pq: PriorityQueue<T>,
    compare: (a: T, b: T) => number
): boolean {
    // Make a copy to test without destroying original
    const copy = pq.clone();
    
    // Invariant 4: Extract ordering
    let previous: T | null = null;
    while (!copy.isEmpty()) {
        const current = copy.extractMin();
        
        if (previous !== null) {
            // Current should be >= previous (for min-heap)
            if (compare(current, previous) < 0) {
                console.error("Invariant violated: extraction not in order");
                return false;
            }
        }
        previous = current;
    }
    
    return true;
}
 
// This test catches subtle bugs in heap implementations
// where the heap property is violated internally

The Heap Property Is an Invariant

When we implement heaps, we'll introduce the 'heap property': every node has priority ≤ its children (for min-heap). This invariant, maintained by insert and extract, is what makes O(log n) operations possible. Invariant thinking is foundational.

Edge Cases and Error Handling

Robust implementations handle edge cases gracefully. Let's catalogue the critical ones:

Empty Queue Operations:

Edge Case: Empty Queue
Operation	Pre-condition Violation	Handling Strategy
extractMin()	Queue is empty (size = 0)	Throw exception / Return undefined / Assert failure
peekMin()	Queue is empty (size = 0)	Same as extract—no element to return
isEmpty()	N/A (always valid)	Return true
size()	N/A (always valid)	Return 0

The Empty Check Pattern:

Good code checks before operating on potentially empty queues:

empty_check_pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Pattern 1: Check before extract (recommended)
if (!pq.isEmpty()) {
    const min = pq.extractMin();
    process(min);
} else {
    handleEmptyQueue();
}
 
// Pattern 2: Try-catch (if exceptions are the API)
try {
    const min = pq.extractMin();
    process(min);
} catch (error) {
    if (error instanceof EmptyQueueError) {
        handleEmptyQueue();
    } else {
        throw error;  // Re-throw unexpected errors
    }
}
 
// Pattern 3: Optional return (TypeScript/modern APIs)
const min = pq.extractMin();  // Returns T | undefined
if (min !== undefined) {
    process(min);
}

Single Element Queue:

The queue with exactly one element is another important edge case:

Single Element Edge Cases

•peek() — Returns the single element (straightforward)
•extract() — Returns the element; queue becomes empty
•After extraction — isEmpty() must return true, size() must return 0
•Heap-specific — Root has no children; heapify-down terminates immediately

Duplicate Handling:

As noted earlier, priority queues typically allow duplicates:

pq.insert(5);
pq.insert(5);
pq.insert(5);

// Queue contains THREE instances of 5
console.log(pq.size());  // 3

pq.extractMin();  // Returns 5, size becomes 2
pq.extractMin();  // Returns 5, size becomes 1
pq.extractMin();  // Returns 5, size becomes 0

Each insert adds a new entry, even if the element/priority already exists. Each extract removes exactly one entry.

Null/Undefined Elements

What if someone inserts null or undefined? The implementation must decide: reject nulls (throw on insert), or allow them (ensure comparison handles nulls). Most robust implementations either forbid nulls or document null semantics clearly. Ambiguity here causes subtle bugs.

Extended Operations — Beyond the Core

The core operations (insert, extract, peek) suffice for many use cases. But real-world applications often need additional capabilities. Let's examine the most important extended operations.

decreaseKey(element, newPriority)

Decreases the priority of an element already in the queue (making it more urgent in a min-heap). This is crucial for algorithms like Dijkstra's shortest path:

// Dijkstra's algorithm skeleton
for each neighbor v of u:
    alt = dist[u] + weight(u, v)
    if alt < dist[v]:
        dist[v] = alt
        pq.decreaseKey(v, alt)  // v's priority decreased

The challenge: how do we find the element to update? The basic heap stores elements without indexing by value. Efficient decreaseKey requires augmenting the heap with a lookup table:

decrease_key.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class IndexedPriorityQueue<T> {
    private heap: Array<{ element: T; priority: number }> = [];
    private indexMap: Map<T, number> = new Map();  // element -> heap index
    
    insert(element: T, priority: number): void {
        const index = this.heap.length;
        this.heap.push({ element, priority });
        this.indexMap.set(element, index);
        this.bubbleUp(index);
    }
    
    decreaseKey(element: T, newPriority: number): void {
        const index = this.indexMap.get(element);
        if (index === undefined) {
            throw new Error("Element not in queue");
        }
        
        const oldPriority = this.heap[index].priority;
        if (newPriority > oldPriority) {
            throw new Error("New priority must be less than current");
        }
        
        this.heap[index].priority = newPriority;
        this.bubbleUp(index);  // Priority decreased → may need to move up
    }
    
    // Must update indexMap during bubbleUp/bubbleDown!
}

increaseKey(element, newPriority)

The opposite of decreaseKey: increases priority (makes less urgent in a min-heap). After increase, the element may need to bubble down instead of up. Less common than decreaseKey but useful in scheduling when task urgency drops.

delete(element)

Removes a specific element regardless of its priority. Useful when:

A scheduled task is cancelled
An element becomes invalid
You need to update an element (delete + insert with new value)

Implementation: decreaseKey to minimum possible value, then extractMin.

delete(element: T): void {
    this.decreaseKey(element, Number.NEGATIVE_INFINITY);
    this.extractMin();  // Will extract the element we just made minimum
}

Extended Operations Complexity (Binary Heap)
Operation	Complexity	Notes
decreaseKey	O(log n)	Requires index tracking; bubbles up
increaseKey	O(log n)	Requires index tracking; bubbles down
delete	O(log n)	decreaseKey + extractMin
contains	O(1)	With hash map for index tracking
merge	O(n + m)	Naively; O(log n) with Fibonacci heaps

Fibonacci Heaps

For algorithms that use decreaseKey heavily (like Dijkstra's), Fibonacci heaps offer O(1) amortized decreaseKey versus O(log n) for binary heaps. However, the constant factors make Fibonacci heaps slower in practice for small inputs. Binary heaps remain the practical choice for most applications.

Interface Design Decisions

When implementing or choosing a priority queue, several design decisions affect usability:

Generic vs Specialized:

Generic: PriorityQueue<T> works with any type; comparator defines ordering
Specialized: IntPriorityQueue optimized for integers; simpler, faster, less flexible

Libraries typically offer generic versions; performance-critical code may use specialized.

Min vs Max Default:

As noted, languages differ. Document your default clearly:

// Explicit is better than implicit
const minHeap = new PriorityQueue<number>({ type: 'min' });
const maxHeap = new PriorityQueue<number>({ type: 'max' });

Bounded vs Unbounded:

Should the queue have a maximum size?

Unbounded: Grows indefinitely; uses dynamic arrays internally
Bounded: Rejects inserts when full; useful for top-K problems and resource limiting

bounded_queue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Bounded priority queue: keeps only top-K elements
class BoundedPriorityQueue<T> {
    private heap: MaxHeap<T>;
    private k: number;
    
    constructor(k: number) {
        this.k = k;
        this.heap = new MaxHeap<T>();
    }
    
    insert(element: T): void {
        if (this.heap.size() < this.k) {
            this.heap.insert(element);
        } else if (element < this.heap.peekMax()) {
            // Element is smaller than max of heap
            // → belongs in top-K
            this.heap.extractMax();  // Remove largest
            this.heap.insert(element);  // Add new element
        }
        // else: element is too large, ignore
    }
    
    // After processing all elements, heap contains K smallest
    getTopK(): T[] {
        return this.heap.toArray();
    }
}

Mutable vs Immutable:

Mutable: Insert/extract modify the queue in place (standard approach)
Immutable: Operations return new queue instances; original unchanged (functional style)

Immutable priority queues exist (often based on leftist heaps or pairing heaps) but are less common. Most production code uses mutable implementations for performance.

Thread Safety:

Concurrent priority queues need synchronization:

External locking: Caller manages locks
Internal locking: Queue methods are synchronized (simpler but coarser)
Lock-free: Advanced implementations avoid locks entirely (complex but scalable)

Know Your Library

Before implementing your own priority queue, check what your language offers. Python's heapq is bare-bones (functions on lists). Java's PriorityQueue is full-featured. C++'s priority_queue is a container adapter. Understanding library semantics saves time and bugs.

Summary — The Priority Queue Contract

We've dissected the priority queue interface with rigor. Let's consolidate:

Interface Summary

•insert(element) — Adds element with its priority; O(log n) target
•extractMin/Max() — Removes and returns extreme element; O(log n) target
•peekMin/Max() — Returns extreme without removing; O(1) target
•Priority can be intrinsic (element value) or extrinsic (separate attribute)
•Stability (FIFO among equal priorities) is not guaranteed by default
•Edge cases: empty queue, single element, duplicates, null handling
•Extended operations: decreaseKey, increaseKey, delete, merge
•Design choices: generics, min/max default, bounded/unbounded, thread safety

What's Next:

We now have a crystal-clear picture of what a priority queue must do. But we haven't addressed how to achieve O(log n) for insert and extract. The next page examines naive implementations—sorted and unsorted arrays—and proves why they fail to meet our complexity targets. This failure sets the stage for the heap, which elegantly solves the problem.

Interface Mastery Achieved

You now understand the priority queue interface at a level of precision that will serve you in interviews, system design, and debugging. You can specify operations formally, reason about invariants, and anticipate edge cases. This foundation is essential before diving into implementation.

2 / 4

Loading learning content...

Data Structures & AlgorithmsPriority Queues Revisited

Priority Queues Revisited — Now with Implementation

LevelIntermediate

Duration60 mins

TopicPriority Queues Revisited

2 / 4

Interface: insert, extractMax/extractMin

The Heart of the Priority Queue

Learning Objectives

The Insert Operation — Adding to the Collection

Formal Definition:

insert(element: T) → void

The insert operation adds an element to the priority queue. After insertion, the element becomes a candidate for extraction according to its priority relative to other elements in the queue.

Semantic Requirements:

Insert Operation Semantics

•Element Inclusion: After insert(x), the queue contains x. Any subsequent extract operations may return x (if it has the appropriate priority).
•Priority Ordering: The element's priority determines its position in the extraction order. Higher-priority elements will be extracted before lower-priority ones.
•No Immediate Extraction: Insert does not extract anything. The queue size increases by exactly one.
•Duplicate Acceptance: Multiple identical elements may be inserted. Each is a separate entry. If x is inserted twice, two extract operations are needed to remove both.

Pre-conditions and Post-conditions:

Thinking in terms of pre-conditions (what must be true before the operation) and post-conditions (what is guaranteed after) helps us reason precisely:

insert_contract.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Insert Operation Contract
 * 
 * Pre-conditions:
 *   - element is a valid T (satisfies the type constraint)
 *   - If priority is separate from element, priority is comparable
 *   - (Optional) Queue is not at maximum capacity
 * 
 * Post-conditions:
 *   - Queue contains one more element than before
 *   - The inserted element is now in the queue
 *   - All previously existing elements are still in the queue
 *   - The relative ordering of existing elements (by priority) is unchanged
 *   - No element has been extracted
 * 
 * Formally, if we denote:
 *   S  = set of elements before insert
 *   S' = set of elements after insert(x)
 * 
 * Then: S' = S ∪ {x} (multiset union, allowing duplicates)
 *       |S'| = |S| + 1
 */
function insert<T>(element: T): void {
    // Implementation follows...
}

Multiset Semantics

Priority Assignment Strategies

When inserting an element, we must associate it with a priority. There are two fundamental approaches:

Approach 1: Intrinsic Priority

The element is its priority. The element type is naturally comparable, and comparison on elements defines the priority ordering.

// Element IS the priority
pq.insert(5);    // Element 5 with implicit priority 5
pq.insert(3);    // Element 3 with implicit priority 3
pq.extractMin(); // Returns 3 (lower value = higher priority in min-heap)

This works well for numeric types, strings, or any type with natural ordering. It's conceptually simple and avoids the overhead of separate priority tracking.

Approach 2: Extrinsic Priority

The element and priority are separate. Each element carries an associated priority value, and comparison on priorities (not elements) determines order.

priority_strategies.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Approach 2: Element with separate priority
interface PrioritizedElement<T> {
    element: T;
    priority: number;
}
 
// Insert tasks with priorities
pq.insert({ element: "Send email", priority: 3 });
pq.insert({ element: "Update database", priority: 1 });
pq.insert({ element: "Generate report", priority: 2 });
 
pq.extractMin(); // Returns "Update database" (priority 1)
pq.extractMin(); // Returns "Generate report" (priority 2)
pq.extractMin(); // Returns "Send email" (priority 3)
 
// Approach 3: Comparison function (most flexible)
interface Task {
    name: string;
    urgency: number;
    deadline: Date;
}
 
// Custom comparator: lower urgency first, ties broken by earlier deadline
const compareTasks = (a: Task, b: Task): number => {
    if (a.urgency !== b.urgency) {
        return a.urgency - b.urgency;
    }
    return a.deadline.getTime() - b.deadline.getTime();
};
 
const taskQueue = new PriorityQueue<Task>(compareTasks);

Trade-offs Between Approaches:

Priority Assignment Strategy Trade-offs
Strategy	Pros	Cons	Best For
Intrinsic (element = priority)	Simple, no extra storage, natural semantics	Limited to comparable types, can't track original elements separately	Numeric algorithms, sorting helpers
Extrinsic (separate priority)	Any element type, clear separation of concerns	Extra storage, must package element with priority	Task scheduling, event systems
Comparator function	Maximum flexibility, complex ordering rules	Function call overhead, harder to debug	Complex domain objects, multi-criteria ordering

Standard Library Patterns

The Extract Operation — Removing the Extreme

Formal Definition:

extractMin() → T    (for min-priority queue)
extractMax() → T    (for max-priority queue)

Semantic Requirements:

Extract Operation Semantics

•Returns Extreme: The returned element must have priority ≤ (for min-heap) or ≥ (for max-heap) all remaining elements.
•Removes Element: After extraction, the returned element is no longer in the queue. Queue size decreases by exactly one.
•Non-Destructive to Others: All other elements remain in the queue with their priorities unchanged.
•Deterministic on Ties: If multiple elements share the same priority, extraction returns one of them (implementation may or may not be stable).
•Requires Non-Empty: Extracting from an empty queue is an error (undefined behavior, exception, or special return value depending on implementation).

extract_contract.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * ExtractMin Operation Contract
 * 
 * Pre-conditions:
 *   - Queue is not empty (size > 0)
 * 
 * Post-conditions:
 *   - Returns element m such that ∀ x ∈ queue: priority(m) ≤ priority(x)
 *   - m is removed from the queue
 *   - |S'| = |S| - 1  (size decreases by 1)
 *   - ∀ x ∈ S, x ≠ m: x ∈ S'  (other elements unchanged)
 * 
 * Error condition:
 *   - If queue is empty: throw Error / return undefined / assertion failure
 * 
 * Formally, if we denote:
 *   S  = multiset of elements before extract
 *   m  = element with minimum priority in S
 *   S' = multiset after extractMin()
 * 
 * Then: m ∈ S
 *       S' = S - {m}  (multiset difference)
 *       return m
 */
function extractMin<T>(): T {
    if (this.isEmpty()) {
        throw new Error("Cannot extract from empty priority queue");
    }
    // Implementation follows...
}

Critical Detail: Stability

What happens when multiple elements have the same priority? Consider:

insert("A", priority=1)
insert("B", priority=1)
insert("C", priority=1)

All three have priority 1. Which is returned by extractMin()?

A stable priority queue preserves insertion order for equal priorities—it returns "A" first, then "B", then "C". A non-stable priority queue may return them in any order.

Most heap implementations are non-stable. The binary heap has no concept of insertion time; it only considers priority. If you need stability, you must engineer it:

stable_priority_queue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Engineering stability: add insertion timestamp as tie-breaker
interface StableElement<T> {
    element: T;
    priority: number;
    insertionOrder: number;  // Ties broken by this
}
 
class StablePriorityQueue<T> {
    private insertCounter = 0;
    
    insert(element: T, priority: number): void {
        this.heap.insert({
            element,
            priority,
            insertionOrder: this.insertCounter++
        });
    }
    
    // Compare: first by priority, then by insertion order
    private compare(a: StableElement<T>, b: StableElement<T>): number {
        if (a.priority !== b.priority) {
            return a.priority - b.priority;
        }
        return a.insertionOrder - b.insertionOrder;  // FIFO for ties
    }
}

Stability Costs

The Peek Operation — Non-Destructive Access

Formal Definition:

peekMin() → T    (for min-priority queue)
peekMax() → T    (for max-priority queue)

Peek returns the same element that extract would return, but without removing it from the queue. The queue remains unchanged.

Why Peek Matters:

At first glance, peek might seem like a convenience operation—just extract and re-insert if you don't want to remove it. But this misses crucial use cases:

Peek Use Cases

•Decision Making: Check the highest-priority task to decide if you should process it now or wait. If priority is 10 (low), maybe sleep. If priority is 1 (critical), process immediately.
•Threshold Checks: Process all elements with priority below threshold. Peek to check, extract if it passes, stop when it doesn't.
•Logging/Monitoring: Log what's about to be processed without affecting the queue state.
•Invariant Checking: In debugging, peek to verify the heap property without mutation.
•Algorithm Requirements: Some algorithms (like merging k sorted lists) need to compare heads of multiple queues without extracting.

peek_use_case.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Use case: Process all tasks until we hit a low-priority one
function processUrgentTasks(pq: PriorityQueue<Task>): void {
    const URGENCY_THRESHOLD = 5;
    
    while (!pq.isEmpty()) {
        // Peek to check without extracting
        const nextTask = pq.peekMin();
        
        if (nextTask.priority > URGENCY_THRESHOLD) {
            // Low-priority task: stop processing, save for later
            console.log(`Stopping: remaining tasks below priority ${URGENCY_THRESHOLD}`);
            break;
        }
        
        // High-priority task: extract and process
        const task = pq.extractMin();
        process(task);
    }
}
 
// Without peek, we'd have to extract and conditionally re-insert!
// That's inefficient and error-prone.

Complexity Expectation:

Peek should be O(1). For a heap, the minimum (or maximum) is always at the root, accessible in constant time. There's no searching, no traversal—just return heap[0].

This is a key advantage of heaps: you always know where the extreme element lives.

Relationship Between Peek and Extract

Operation Interplay — Invariants Across Operations

Operations don't exist in isolation. A correct priority queue implementation must maintain invariants across operations. Let's formalize these cross-operation invariants.

Invariant 1: Size Consistency

size_after_insert = size_before_insert + 1
size_after_extract = size_before_extract - 1
size_after_peek = size_before_peek (unchanged)

Invariant 2: Peek-Extract Consistency

Let x = peekMin()
Let y = extractMin()
Then: x == y (same element returned)

Whatever peek returns, extract must return the same element (assuming no intervening operations).

Invariant 3: Extremal Property

After any sequence of operations:

∀ x ∈ queue: priority(peekMin()) ≤ priority(x)

The element returned by peek always has the minimum priority among all elements.

Invariant 4: Extract Ordering

If you extract all elements from a priority queue, they come out in sorted order (by priority).

const results: number[] = [];
while (!pq.isEmpty()) {
    results.push(pq.extractMin());
}
// results is sorted in ascending order (for min-heap)

invariant_testing.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Testing priority queue invariants
function verifyPriorityQueueInvariants<T>(
    pq: PriorityQueue<T>,
    compare: (a: T, b: T) => number
): boolean {
    // Make a copy to test without destroying original
    const copy = pq.clone();
    
    // Invariant 4: Extract ordering
    let previous: T | null = null;
    while (!copy.isEmpty()) {
        const current = copy.extractMin();
        
        if (previous !== null) {
            // Current should be >= previous (for min-heap)
            if (compare(current, previous) < 0) {
                console.error("Invariant violated: extraction not in order");
                return false;
            }
        }
        previous = current;
    }
    
    return true;
}
 
// This test catches subtle bugs in heap implementations
// where the heap property is violated internally

The Heap Property Is an Invariant

Edge Cases and Error Handling

Robust implementations handle edge cases gracefully. Let's catalogue the critical ones:

Empty Queue Operations:

Edge Case: Empty Queue
Operation	Pre-condition Violation	Handling Strategy
extractMin()	Queue is empty (size = 0)	Throw exception / Return undefined / Assert failure
peekMin()	Queue is empty (size = 0)	Same as extract—no element to return
isEmpty()	N/A (always valid)	Return true
size()	N/A (always valid)	Return 0

The Empty Check Pattern:

Good code checks before operating on potentially empty queues:

empty_check_pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Pattern 1: Check before extract (recommended)
if (!pq.isEmpty()) {
    const min = pq.extractMin();
    process(min);
} else {
    handleEmptyQueue();
}
 
// Pattern 2: Try-catch (if exceptions are the API)
try {
    const min = pq.extractMin();
    process(min);
} catch (error) {
    if (error instanceof EmptyQueueError) {
        handleEmptyQueue();
    } else {
        throw error;  // Re-throw unexpected errors
    }
}
 
// Pattern 3: Optional return (TypeScript/modern APIs)
const min = pq.extractMin();  // Returns T | undefined
if (min !== undefined) {
    process(min);
}

Single Element Queue:

The queue with exactly one element is another important edge case:

Single Element Edge Cases

•peek() — Returns the single element (straightforward)
•extract() — Returns the element; queue becomes empty
•After extraction — isEmpty() must return true, size() must return 0
•Heap-specific — Root has no children; heapify-down terminates immediately

Duplicate Handling:

As noted earlier, priority queues typically allow duplicates:

pq.insert(5);
pq.insert(5);
pq.insert(5);

// Queue contains THREE instances of 5
console.log(pq.size());  // 3

pq.extractMin();  // Returns 5, size becomes 2
pq.extractMin();  // Returns 5, size becomes 1
pq.extractMin();  // Returns 5, size becomes 0

Each insert adds a new entry, even if the element/priority already exists. Each extract removes exactly one entry.

Null/Undefined Elements

Extended Operations — Beyond the Core

The core operations (insert, extract, peek) suffice for many use cases. But real-world applications often need additional capabilities. Let's examine the most important extended operations.

decreaseKey(element, newPriority)

Decreases the priority of an element already in the queue (making it more urgent in a min-heap). This is crucial for algorithms like Dijkstra's shortest path:

// Dijkstra's algorithm skeleton
for each neighbor v of u:
    alt = dist[u] + weight(u, v)
    if alt < dist[v]:
        dist[v] = alt
        pq.decreaseKey(v, alt)  // v's priority decreased

The challenge: how do we find the element to update? The basic heap stores elements without indexing by value. Efficient decreaseKey requires augmenting the heap with a lookup table:

decrease_key.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class IndexedPriorityQueue<T> {
    private heap: Array<{ element: T; priority: number }> = [];
    private indexMap: Map<T, number> = new Map();  // element -> heap index
    
    insert(element: T, priority: number): void {
        const index = this.heap.length;
        this.heap.push({ element, priority });
        this.indexMap.set(element, index);
        this.bubbleUp(index);
    }
    
    decreaseKey(element: T, newPriority: number): void {
        const index = this.indexMap.get(element);
        if (index === undefined) {
            throw new Error("Element not in queue");
        }
        
        const oldPriority = this.heap[index].priority;
        if (newPriority > oldPriority) {
            throw new Error("New priority must be less than current");
        }
        
        this.heap[index].priority = newPriority;
        this.bubbleUp(index);  // Priority decreased → may need to move up
    }
    
    // Must update indexMap during bubbleUp/bubbleDown!
}

increaseKey(element, newPriority)

delete(element)

Removes a specific element regardless of its priority. Useful when:

A scheduled task is cancelled
An element becomes invalid
You need to update an element (delete + insert with new value)

Implementation: decreaseKey to minimum possible value, then extractMin.

delete(element: T): void {
    this.decreaseKey(element, Number.NEGATIVE_INFINITY);
    this.extractMin();  // Will extract the element we just made minimum
}

Extended Operations Complexity (Binary Heap)
Operation	Complexity	Notes
decreaseKey	O(log n)	Requires index tracking; bubbles up
increaseKey	O(log n)	Requires index tracking; bubbles down
delete	O(log n)	decreaseKey + extractMin
contains	O(1)	With hash map for index tracking
merge	O(n + m)	Naively; O(log n) with Fibonacci heaps

Fibonacci Heaps

Interface Design Decisions

When implementing or choosing a priority queue, several design decisions affect usability:

Generic vs Specialized:

Generic: PriorityQueue<T> works with any type; comparator defines ordering
Specialized: IntPriorityQueue optimized for integers; simpler, faster, less flexible

Libraries typically offer generic versions; performance-critical code may use specialized.

Min vs Max Default:

As noted, languages differ. Document your default clearly:

// Explicit is better than implicit
const minHeap = new PriorityQueue<number>({ type: 'min' });
const maxHeap = new PriorityQueue<number>({ type: 'max' });

Bounded vs Unbounded:

Should the queue have a maximum size?

Unbounded: Grows indefinitely; uses dynamic arrays internally
Bounded: Rejects inserts when full; useful for top-K problems and resource limiting

bounded_queue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Bounded priority queue: keeps only top-K elements
class BoundedPriorityQueue<T> {
    private heap: MaxHeap<T>;
    private k: number;
    
    constructor(k: number) {
        this.k = k;
        this.heap = new MaxHeap<T>();
    }
    
    insert(element: T): void {
        if (this.heap.size() < this.k) {
            this.heap.insert(element);
        } else if (element < this.heap.peekMax()) {
            // Element is smaller than max of heap
            // → belongs in top-K
            this.heap.extractMax();  // Remove largest
            this.heap.insert(element);  // Add new element
        }
        // else: element is too large, ignore
    }
    
    // After processing all elements, heap contains K smallest
    getTopK(): T[] {
        return this.heap.toArray();
    }
}

Mutable vs Immutable:

Mutable: Insert/extract modify the queue in place (standard approach)
Immutable: Operations return new queue instances; original unchanged (functional style)

Immutable priority queues exist (often based on leftist heaps or pairing heaps) but are less common. Most production code uses mutable implementations for performance.

Thread Safety:

Concurrent priority queues need synchronization:

External locking: Caller manages locks
Internal locking: Queue methods are synchronized (simpler but coarser)
Lock-free: Advanced implementations avoid locks entirely (complex but scalable)

Know Your Library

Summary — The Priority Queue Contract

We've dissected the priority queue interface with rigor. Let's consolidate:

Interface Summary

•insert(element) — Adds element with its priority; O(log n) target
•extractMin/Max() — Removes and returns extreme element; O(log n) target
•peekMin/Max() — Returns extreme without removing; O(1) target
•Priority can be intrinsic (element value) or extrinsic (separate attribute)
•Stability (FIFO among equal priorities) is not guaranteed by default
•Edge cases: empty queue, single element, duplicates, null handling
•Extended operations: decreaseKey, increaseKey, delete, merge
•Design choices: generics, min/max default, bounded/unbounded, thread safety

What's Next:

Interface Mastery Achieved

2 / 4