Priority Queue Intro - Learning Module

Loading content...

0/276

Interface — Insert with Priority, Remove Highest Priority

The Contract That Defines Behavior

Every abstract data type is defined not by its implementation, but by its interface—the set of operations it supports and the behaviors those operations guarantee. For priority queues, this interface is elegantly minimal yet remarkably powerful.

At its core, a priority queue promises just two primary capabilities:

Insert an element with a priority — Add something to the collection, tagged with its importance
Remove and return the highest-priority element — Extract the most important item

From these two operations, augmented by a few helper methods, we can build scheduling systems, power graph algorithms, implement compression, and solve countless other problems.

This page provides a comprehensive specification of the priority queue interface, examining each operation in depth, understanding its semantics, preconditions, postconditions, and proper usage patterns.

What You Will Learn

By the end of this page, you will understand every operation in the priority queue interface: insert (enqueue), extractMin/extractMax (dequeue), peek, isEmpty, and size. You'll know their time complexities, edge cases, error handling conventions, and how they combine in real usage patterns. This knowledge forms the foundation for using priority queues effectively in any programming language.

The Complete Priority Queue Interface

Before diving into individual operations, let's see the complete interface specification. This provides an overview that we'll then explore operation by operation.

Core Operations (Essential):

insert(element, priority) — Add element with given priority
extractMin() / extractMax() — Remove and return extreme priority element
peek() / findMin() / findMax() — View extreme element without removing
isEmpty() — Check if collection is empty
size() — Return number of elements

Extended Operations (Common but not universal):

decreaseKey(element, newPriority) — Lower an element's priority (used in Dijkstra's)
increaseKey(element, newPriority) — Raise an element's priority
remove(element) — Remove arbitrary element (not just min/max)
contains(element) — Check if element exists
clear() — Remove all elements

complete-priority-queue-interface
TypeScript
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
 * Complete Priority Queue Interface Specification
 * 
 * This interface defines a min-priority queue where lower priority
 * values indicate higher importance (extracted first).
 * 
 * @template T - The type of elements stored in the priority queue
 */
interface PriorityQueue<T> {
    // ========== Core Operations ==========
    
    /**
     * Inserts an element with the specified priority.
     * 
     * @param element - The element to insert
     * @param priority - The priority value (lower = more important)
     * @throws Error if priority is not a valid comparable value
     * 
     * Time Complexity: O(log n) for heap-based implementations
     */
    insert(element: T, priority: number): void;
    
    /**
     * Removes and returns the element with minimum priority.
     * 
     * @returns The element with lowest priority value
     * @throws Error if the queue is empty
     * 
     * Time Complexity: O(log n) for heap-based implementations
     */
    extractMin(): T;
    
    /**
     * Returns the element with minimum priority without removing it.
     * 
     * @returns The element with lowest priority value
     * @throws Error if the queue is empty
     * 
     * Time Complexity: O(1)
     */
    peek(): T;
    
    /**
     * Checks whether the priority queue contains any elements.
     * 
     * @returns true if empty, false otherwise
     * 
     * Time Complexity: O(1)
     */
    isEmpty(): boolean;
    
    /**
     * Returns the number of elements in the priority queue.
     * 
     * @returns Element count
     * 
     * Time Complexity: O(1)
     */
    size(): number;
    
    // ========== Extended Operations ==========
    
    /**
     * Decreases the priority of an existing element.
     * Used by algorithms like Dijkstra's shortest path.
     * 
     * @param element - The element whose priority to decrease
     * @param newPriority - The new (lower) priority value
     * @throws Error if element not found or newPriority >= current priority
     * 
     * Time Complexity: O(log n) for indexed binary heap
     *                  O(1) amortized for Fibonacci heap
     */
    decreaseKey?(element: T, newPriority: number): void;
    
    /**
     * Removes a specific element from the queue (not necessarily the minimum).
     * 
     * @param element - The element to remove
     * @returns true if element was found and removed, false otherwise
     * 
     * Time Complexity: O(n) for basic heap (find) + O(log n) for removal
     *                  O(log n) for indexed heap
     */
    remove?(element: T): boolean;
    
    /**
     * Checks whether a specific element exists in the queue.
     * 
     * @param element - The element to search for
     * @returns true if element is in the queue, false otherwise
     * 
     * Time Complexity: O(n) for basic heap, O(1) for indexed heap
     */
    contains?(element: T): boolean;
    
    /**
     * Removes all elements from the priority queue.
     * 
     * Time Complexity: O(1) or O(n) depending on memory management
     */
    clear?(): void;
}

The Insert Operation

The insert operation (also called push, enqueue, or add in various libraries) is the primary way to add elements to a priority queue. Let's examine it comprehensively.

Operation Semantics:

insert(element: T, priority: P) → void

Preconditions:

The priority value must be comparable (typically numeric)
Element may or may not be required to be unique (implementation-dependent)
Queue has capacity (for bounded implementations)

Postconditions:

Element is now in the queue
Queue size increased by 1
The heap invariant is maintained
The element will be returned by extractMin when no lower-priority elements exist

Insert Operation Details

•Time Complexity — O(log n) for binary heaps. The element is added at the end and 'bubbles up' to its correct position, visiting at most log₂(n) levels.
•Space Complexity — O(1) additional space (the element is stored, but no auxiliary structures needed for the operation itself).
•Duplicate Handling — Most priority queues allow duplicates. If you insert the same element twice, it exists twice with potentially different priorities.
•Priority Coupling — Some APIs couple element and priority (insert(element, priority)), others expect comparable elements where priority is inherent (insert(comparableElement)).

insert-operation-examples
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Example 1: Basic insert with explicit priority
const taskQueue = new PriorityQueue<string>();
 
taskQueue.insert("Email notification", 5);    // Low priority (5)
taskQueue.insert("Security alert", 1);        // High priority (1)
taskQueue.insert("Database backup", 3);       // Medium priority (3)
 
// Queue state: Security alert will be extracted first
 
// Example 2: Insert with derived priority
interface ScheduledTask {
    name: string;
    deadline: Date;
}
 
const scheduler = new PriorityQueue<ScheduledTask>();
 
const task1: ScheduledTask = {
    name: "Submit report",
    deadline: new Date("2024-01-15")
};
 
// Priority is the deadline timestamp (earlier = more urgent)
scheduler.insert(task1, task1.deadline.getTime());
 
// Example 3: Handling insert edge cases
function safeInsert<T>(
    queue: PriorityQueue<T>,
    element: T,
    priority: number
): boolean {
    // Validate priority
    if (!Number.isFinite(priority)) {
        console.error("Priority must be a finite number");
        return false;
    }
    
    // Check for NaN
    if (Number.isNaN(priority)) {
        console.error("Priority cannot be NaN");
        return false;
    }
    
    try {
        queue.insert(element, priority);
        return true;
    } catch (error) {
        console.error("Insert failed:", error);
        return false;
    }
}

Mutable Priority Pitfall

If an element's priority is derived from a mutable property, changing that property after insertion breaks the heap invariant. The priority queue has no way to know the priority changed. Either use immutable priority values, or explicitly use decreaseKey/increaseKey operations when priorities change.

The Extract Operation

The extractMin (or extractMax) operation is the heart of the priority queue—it removes and returns the highest-priority element. This is where the priority queue delivers its core value proposition.

Operation Semantics:

extractMin() → T    // For min-priority queue
extractMax() → T    // For max-priority queue

Alternative Names:

poll() (Java)
heappop() (Python's heapq)
pop() or top() combined with removal
dequeue() (drawing parallel to standard queues)

Extract Operation Details

•Time Complexity — O(log n) for binary heaps. After removing the root, the last element takes its place and 'bubbles down' to restore the heap property.
•Empty Queue Behavior — Critical design decision! Options: throw exception, return null/undefined, return Optional/Maybe. Know your library's convention.
•Destructive Operation — Unlike peek, extract modifies the queue. The element is gone after extraction. If you need to re-examine, use peek first.
•Tie-Breaking — When multiple elements share the minimum priority, which one is returned? Implementation-dependent. Stable queues return the earliest inserted.

extract-operation-examples
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Safe extraction patterns
 
class SafePriorityQueue<T> {
    private heap: Array<{ element: T; priority: number }> = [];
    
    /**
     * Extract minimum - throws on empty queue
     * Use when: empty queue is a programming error
     */
    extractMin(): T {
        if (this.isEmpty()) {
            throw new Error("Cannot extract from empty priority queue");
        }
        return this.doExtract();
    }
    
    /**
     * Try extract - returns undefined on empty queue
     * Use when: empty queue is a normal condition
     */
    tryExtractMin(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.doExtract();
    }
    
    /**
     * Extract with result wrapper
     * Use when: you want explicit success/failure handling
     */
    extractMinResult(): { success: true; value: T } | { success: false } {
        if (this.isEmpty()) {
            return { success: false };
        }
        return { success: true, value: this.doExtract() };
    }
    
    private doExtract(): T {
        const min = this.heap[0].element;
        const last = this.heap.pop()!;
        
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        
        return min;
    }
    
    isEmpty(): boolean {
        return this.heap.length === 0;
    }
    
    private bubbleDown(index: number): void {
        // Implementation details...
    }
}
 
// Usage patterns
const pq = new SafePriorityQueue<string>();
pq.insert("task1", 1);
pq.insert("task2", 2);
 
// Pattern 1: Check then extract (two operations, potential race condition)
if (!pq.isEmpty()) {
    const task = pq.extractMin();
    processTask(task);
}
 
// Pattern 2: Try extract (single operation, null check required)
const maybeTask = pq.tryExtractMin();
if (maybeTask !== undefined) {
    processTask(maybeTask);
}
 
// Pattern 3: Extract until empty (common loop pattern)
while (!pq.isEmpty()) {
    const task = pq.extractMin();
    processTask(task);
}
 
// Pattern 4: Process N items or until empty
function processUpToN<T>(queue: SafePriorityQueue<T>, n: number): T[] {
    const results: T[] = [];
    for (let i = 0; i < n && !queue.isEmpty(); i++) {
        results.push(queue.extractMin());
    }
    return results;
}
 
function processTask(task: string): void {
    console.log(`Processing: ${task}`);
}

Extraction Order is the Output

The sequence of elements returned by repeated extractMin calls gives elements in priority order. This is how heapsort works: insert all elements, then extract until empty. The extraction sequence is the sorted sequence. Time: O(n log n).

The Peek Operation

The peek operation (also called findMin, top, or front) allows inspection of the highest-priority element without removing it. This read-only operation is essential for decision-making without commitment.

Operation Semantics:

peek() → T    // Returns minimum/maximum without removal

Why Peek Matters:

Peek enables important patterns:

Conditional Processing — Examine the next item before deciding whether to process it
Threshold Checking — Is the top priority above/below a threshold?
Monitoring — Report what's coming next without affecting the queue
Algorithm Correctness — Some algorithms need to inspect without extracting

Peek Operation Details

•Time Complexity — O(1). The minimum/maximum is always at the root (index 0 for array-based heaps). No traversal needed.
•Non-Destructive — The queue state is unchanged. Calling peek multiple times returns the same element.
•Empty Queue Handling — Same considerations as extract. Throw, return null, or use Optional wrapper.
•Reference vs Value — Peek typically returns a reference to the actual element. Modifying it (especially priority-related fields) can corrupt the heap!

peek-operation-examples
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
interface Task {
    id: string;
    priority: number;
    deadline: Date;
}
 
class TaskScheduler {
    private queue: PriorityQueue<Task>;
    private currentTime: Date;
    
    constructor() {
        this.queue = new PriorityQueue<Task>();
        this.currentTime = new Date();
    }
    
    /**
     * Pattern 1: Conditional processing based on peek
     * Only process if the top task is ready
     */
    processIfReady(): Task | null {
        if (this.queue.isEmpty()) {
            return null;
        }
        
        const nextTask = this.queue.peek();
        
        // Check if task is ready to be processed
        if (nextTask.deadline <= this.currentTime) {
            // Deadline has passed, process immediately
            return this.queue.extractMin();
        }
        
        // Not ready yet, don't extract
        return null;
    }
    
    /**
     * Pattern 2: Batch processing with priority threshold
     * Process all high-priority items (priority < threshold)
     */
    processHighPriority(threshold: number): Task[] {
        const processed: Task[] = [];
        
        // Keep processing while queue has items below threshold
        while (!this.queue.isEmpty() && 
               this.queue.peek().priority < threshold) {
            processed.push(this.queue.extractMin());
        }
        
        return processed;
    }
    
    /**
     * Pattern 3: Time-until-next calculation
     * How long until the next task is due?
     */
    timeUntilNext(): number | null {
        if (this.queue.isEmpty()) {
            return null;  // No tasks pending
        }
        
        const nextTask = this.queue.peek();
        const msUntilDeadline = nextTask.deadline.getTime() - 
                                this.currentTime.getTime();
        
        return Math.max(0, msUntilDeadline);
    }
    
    /**
     * Pattern 4: Peek for logging/monitoring
     */
    logQueueStatus(): void {
        if (this.queue.isEmpty()) {
            console.log("Queue is empty");
            return;
        }
        
        const top = this.queue.peek();
        console.log(`Queue size: ${this.queue.size()}`);
        console.log(`Next task: ${top.id} (priority ${top.priority})`);
        console.log(`Due: ${top.deadline.toISOString()}`);
        // Queue unchanged after logging
    }
}

Peek and Immutability

For safety, some implementations return a copy or an immutable view from peek. This prevents accidental corruption of the heap. In performance-critical code, this copy overhead might matter. Know your library's behavior and consider defensive copying if returning mutable references.

The isEmpty and Size Operations

While less glamorous than insert and extract, the isEmpty and size operations are essential for control flow and handling edge cases. Let's examine them with the rigor they deserve.

isEmpty Operation:

isEmpty() → boolean

size Operation:

size() → integer

Both are O(1) operations in all reasonable implementations—the size is tracked as elements are inserted and extracted.

Why Two Operations?

You might ask: "Why have isEmpty when we can just check size() === 0?" Several reasons:

Reasons for Separate isEmpty

•Semantic Clarity — isEmpty() clearly expresses intent. size() === 0 requires the reader to parse an equality check.
•Potential Optimization — For some data structures, checking emptiness can be faster than computing full size. (Not relevant for heaps, but matters for consistency across ADTs.)
•Null/Undefined Safety — isEmpty() returns a definite boolean. size() returns a number that must be compared.
•Convention — Most collection APIs include isEmpty. Consistency aids learnability.

isempty-size-patterns
TypeScript
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Common patterns using isEmpty and size
 
function drainQueue<T>(queue: PriorityQueue<T>): T[] {
    const results: T[] = [];
    
    while (!queue.isEmpty()) {
        results.push(queue.extractMin());
    }
    
    return results;
}
 
function processWithLimit<T>(
    queue: PriorityQueue<T>,
    maxItems: number
): T[] {
    const results: T[] = [];
    
    // Use size for limiting, isEmpty for existence check
    const toProcess = Math.min(maxItems, queue.size());
    
    for (let i = 0; i < toProcess; i++) {
        results.push(queue.extractMin());
    }
    
    return results;
}
 
function reportQueueHealth<T>(queue: PriorityQueue<T>): string {
    if (queue.isEmpty()) {
        return "Queue is empty - no pending work";
    }
    
    const size = queue.size();
    
    if (size < 10) {
        return `Queue healthy: ${size} items`;
    } else if (size < 100) {
        return `Queue growing: ${size} items - consider scaling`;
    } else {
        return `Queue critical: ${size} items - immediate attention needed`;
    }
}
 
// Pattern: Guard clause with isEmpty
function processNext<T>(queue: PriorityQueue<T>): T | null {
    if (queue.isEmpty()) {
        return null;  // Early return for empty queue
    }
    
    return queue.extractMin();
}
 
// Pattern: Batch size calculation
function calculateBatchSize<T>(
    queue: PriorityQueue<T>,
    preferredBatch: number
): number {
    // Take preferred batch size or remaining items, whichever is smaller
    return Math.min(preferredBatch, queue.size());
}
 
// Pattern: Progress reporting
function processWithProgress<T>(
    queue: PriorityQueue<T>,
    process: (item: T) => void
): void {
    const total = queue.size();
    let processed = 0;
    
    while (!queue.isEmpty()) {
        process(queue.extractMin());
        processed++;
        
        // Report progress every 10%
        if (processed % Math.ceil(total / 10) === 0) {
            console.log(`Progress: ${processed}/${total} (${
                Math.round(processed / total * 100)
            }%)`);
        }
    }
    
    console.log("Processing complete!");
}

Concurrency Warning

In concurrent environments, checking isEmpty then extracting is NOT atomic. Another thread could extract between your check and operation. Use thread-safe priority queue implementations or proper synchronization. Some libraries offer atomic tryPop or pollWithTimeout operations.

Extended Operations: decreaseKey, remove, contains

Beyond the core operations, many priority queue implementations offer extended operations that enable more sophisticated use cases. These are often crucial for specific algorithms.

decreaseKey (or increasePriority):

This operation lowers the priority value of an existing element (which, in a min-heap, means it becomes more important). It's essential for algorithms like Dijkstra's shortest path.

decreaseKey(element, newPriority) → void

Time Complexity:

O(n) for basic heap (must find element first)
O(log n) for indexed heap (direct lookup via auxiliary map)

extended-operations
TypeScript
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**
 * Indexed Priority Queue with full extended operations
 */
class IndexedPriorityQueue<K, V> {
    private heap: Array<{ key: K; value: V; priority: number }> = [];
    private keyToIndex: Map<K, number> = new Map();
    
    // Core operations...
    insert(key: K, value: V, priority: number): void { /* ... */ }
    extractMin(): { key: K; value: V; priority: number } | undefined { /* ... */ }
    peek(): { key: K; value: V; priority: number } | undefined { /* ... */ }
    isEmpty(): boolean { return this.heap.length === 0; }
    size(): number { return this.heap.length; }
    
    /**
     * Decrease the priority of an existing element.
     * Critical for Dijkstra's algorithm.
     * 
     * @throws Error if key not found or new priority is not lower
     */
    decreaseKey(key: K, newPriority: number): void {
        const index = this.keyToIndex.get(key);
        
        if (index === undefined) {
            throw new Error(`Key not found: ${String(key)}`);
        }
        
        const currentPriority = this.heap[index].priority;
        
        if (newPriority >= currentPriority) {
            throw new Error(
                `New priority (${newPriority}) must be less than ` +
                                        `current (${currentPriority})`
            );
        }
        
        this.heap[index].priority = newPriority;
        this.bubbleUp(index);  // Priority improved, might need to rise
    }
    
    /**
     * Increase the priority of an existing element.
     * Less common, but useful for aging or demotion.
     */
    increaseKey(key: K, newPriority: number): void {
        const index = this.keyToIndex.get(key);
        
        if (index === undefined) {
            throw new Error(`Key not found: ${String(key)}`);
        }
        
        const currentPriority = this.heap[index].priority;
        
        if (newPriority <= currentPriority) {
            throw new Error(
                `New priority (${newPriority}) must be greater than current (${currentPriority})`
            );
        }
        
        this.heap[index].priority = newPriority;
        this.bubbleDown(index);  // Priority worsened, might need to sink
    }
    
    /**
     * Check if a key exists in the queue.
     */
    contains(key: K): boolean {
        return this.keyToIndex.has(key);
    }
    
    /**
     * Remove an arbitrary element (not just the minimum).
     */
    remove(key: K): boolean {
        const index = this.keyToIndex.get(key);
        
        if (index === undefined) {
            return false;  // Key not found
        }
        
        // Strategy: decrease key to -Infinity, then extract
        // This is cleaner than handling the general remove case
        this.heap[index].priority = Number.NEGATIVE_INFINITY;
        this.bubbleUp(index);  // Now at root
        this.extractMin();     // Remove it
        
        return true;
    }
    
    /**
     * Get the current priority of a key.
     */
    getPriority(key: K): number | undefined {
        const index = this.keyToIndex.get(key);
        return index !== undefined ? this.heap[index].priority : undefined;
    }
    
    /**
     * Insert or update: if key exists, update priority; else insert.
     */
    upsert(key: K, value: V, priority: number): void {
        if (this.contains(key)) {
            const currentPriority = this.getPriority(key)!;
            if (priority < currentPriority) {
                this.decreaseKey(key, priority);
            } else if (priority > currentPriority) {
                this.increaseKey(key, priority);
            }
            // If equal, nothing to do
        } else {
            this.insert(key, value, priority);
        }
    }
    
    // Helper methods for heap maintenance
    private bubbleUp(index: number): void { /* ... */ }
    private bubbleDown(index: number): void { /* ... */ }
    private swap(i: number, j: number): void { /* ... */ }
}

Dijkstra's Algorithm — Why decreaseKey Matters:

In Dijkstra's shortest path algorithm, when we find a shorter path to a vertex, we need to update its tentative distance in the priority queue. Without decreaseKey:

Option 1: Insert duplicates and ignore stale entries (memory wasteful)
Option 2: Remove and re-insert (O(n) to find for basic heap)

With decreaseKey in an indexed heap:

O(log n) priority update directly
No duplicates needed
Clean, efficient implementation

This is why indexed priority queues (where we can look up elements by key in O(1)) are used for graph algorithms.

Library Support Varies

Not all standard library priority queues support decreaseKey. Java's PriorityQueue does not. Python's heapq is just functions on lists—no decreaseKey. You may need to implement an indexed priority queue yourself or use a third-party library for algorithms requiring this operation.

Priority Queues in Standard Libraries

Different programming languages provide different APIs for priority queues. Understanding these variations helps you work effectively across languages and choose appropriate implementations.

Key Differences to Watch:

Min-heap vs max-heap default
Naming conventions (add vs insert vs push)
Error handling (exceptions vs null)
Support for extended operations

Priority Queue APIs Across Languages
Language	Class/Module	Default Order	Insert	Extract	Peek
Python	heapq	Min-heap	heappush(h, x)	heappop(h)	h[0]
Java	PriorityQueue	Min-heap	add(e) / offer(e)	poll() / remove()	peek()
C++	priority_queue	Max-heap	push(x)	pop() + top()	top()
C#	PriorityQueue<T,P>	Min-heap	Enqueue(e, p)	Dequeue()	Peek()
Go	container/heap	Min-heap*	Push(h, x)	Pop(h)	h[0] / (*h)[0]
Rust	BinaryHeap	Max-heap	push(x)	pop()	peek()

language-comparison
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
32
33
34
35
36
37
38
39
40
41
// JavaScript/TypeScript has NO built-in priority queue!
// Common options:
// 1. Implement your own
// 2. Use a library (e.g., @datastructures-js/priority-queue)
 
// Example with @datastructures-js/priority-queue
import { 
    MinPriorityQueue, 
    MaxPriorityQueue 
} from '@datastructures-js/priority-queue';
 
// Min priority queue (number elements)
const minQueue = new MinPriorityQueue<number>();
minQueue.enqueue(5);
minQueue.enqueue(2);
minQueue.enqueue(8);
 
console.log(minQueue.dequeue()); // { priority: 2, element: 2 }
console.log(minQueue.front());   // { priority: 5, element: 5 }
 
// With custom priority function
const taskQueue = new MinPriorityQueue<Task>(task => task.priority);
taskQueue.enqueue({ id: "1", priority: 5 });
taskQueue.enqueue({ id: "2", priority: 2 });
 
// Simple array-based implementation for quick needs
class SimplePQ<T> {
    private items: Array<{ element: T; priority: number }> = [];
    
    enqueue(element: T, priority: number): void {
        this.items.push({ element, priority });
        this.items.sort((a, b) => a.priority - b.priority);
    }
    
    dequeue(): T | undefined {
        return this.items.shift()?.element;
    }
    
    // Note: O(n log n) insert due to sorting - not efficient!
    // Use proper heap for production
}

C++ Gotcha: pop() Doesn't Return

In C++ STL, priority_queue::pop() returns void, not the element. You must call top() first to get the value, then pop() to remove it. This design allows exception safety—if copying the return value throws, the queue state is unchanged.

Summary: The Priority Queue Interface

We've comprehensively covered the priority queue interface—the operations that define this abstract data type regardless of implementation. Let's consolidate our understanding.

Key Takeaways

•Core operations are minimal — insert, extractMin/Max, peek, isEmpty, size. This small interface provides enormous power.
•insert is O(log n) — Elements bubble up to their correct position, visiting at most log₂(n) levels.
•extractMin is O(log n) — The replacement element bubbles down, restoring the heap property.
•peek is O(1) — The extreme element is always at the root, accessible instantly.
•Extended operations enable algorithms — decreaseKey is crucial for Dijkstra's; contains and remove support more flexible usage.
•Error handling varies — Know whether your library throws, returns null, or uses Optional for empty-queue operations.
•Standard libraries differ significantly — Default ordering (min vs max), method names, and supported operations vary by language.

What's Next:

With the interface fully specified, it's natural to ask: how do we implement this interface efficiently? The next page previews the heap data structure—the elegant, array-based tree that makes priority queues practical. This preview sets the stage for the dedicated Heaps chapter where we'll explore heaps in complete detail.

Page Complete

You now have a complete understanding of the priority queue interface. You know every operation—its semantics, time complexity, edge cases, and proper usage patterns. This knowledge enables you to use priority queues effectively in any programming language and prepares you for understanding their implementation.

Interface — Insert with Priority, Remove Highest Priority

The Contract That Defines Behavior

At its core, a priority queue promises just two primary capabilities:

Insert an element with a priority — Add something to the collection, tagged with its importance
Remove and return the highest-priority element — Extract the most important item

From these two operations, augmented by a few helper methods, we can build scheduling systems, power graph algorithms, implement compression, and solve countless other problems.

What You Will Learn

The Complete Priority Queue Interface

Before diving into individual operations, let's see the complete interface specification. This provides an overview that we'll then explore operation by operation.

Core Operations (Essential):

insert(element, priority) — Add element with given priority
extractMin() / extractMax() — Remove and return extreme priority element
peek() / findMin() / findMax() — View extreme element without removing
isEmpty() — Check if collection is empty
size() — Return number of elements

Extended Operations (Common but not universal):

decreaseKey(element, newPriority) — Lower an element's priority (used in Dijkstra's)
increaseKey(element, newPriority) — Raise an element's priority
remove(element) — Remove arbitrary element (not just min/max)
contains(element) — Check if element exists
clear() — Remove all elements

complete-priority-queue-interface
TypeScript
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
 * Complete Priority Queue Interface Specification
 * 
 * This interface defines a min-priority queue where lower priority
 * values indicate higher importance (extracted first).
 * 
 * @template T - The type of elements stored in the priority queue
 */
interface PriorityQueue<T> {
    // ========== Core Operations ==========
    
    /**
     * Inserts an element with the specified priority.
     * 
     * @param element - The element to insert
     * @param priority - The priority value (lower = more important)
     * @throws Error if priority is not a valid comparable value
     * 
     * Time Complexity: O(log n) for heap-based implementations
     */
    insert(element: T, priority: number): void;
    
    /**
     * Removes and returns the element with minimum priority.
     * 
     * @returns The element with lowest priority value
     * @throws Error if the queue is empty
     * 
     * Time Complexity: O(log n) for heap-based implementations
     */
    extractMin(): T;
    
    /**
     * Returns the element with minimum priority without removing it.
     * 
     * @returns The element with lowest priority value
     * @throws Error if the queue is empty
     * 
     * Time Complexity: O(1)
     */
    peek(): T;
    
    /**
     * Checks whether the priority queue contains any elements.
     * 
     * @returns true if empty, false otherwise
     * 
     * Time Complexity: O(1)
     */
    isEmpty(): boolean;
    
    /**
     * Returns the number of elements in the priority queue.
     * 
     * @returns Element count
     * 
     * Time Complexity: O(1)
     */
    size(): number;
    
    // ========== Extended Operations ==========
    
    /**
     * Decreases the priority of an existing element.
     * Used by algorithms like Dijkstra's shortest path.
     * 
     * @param element - The element whose priority to decrease
     * @param newPriority - The new (lower) priority value
     * @throws Error if element not found or newPriority >= current priority
     * 
     * Time Complexity: O(log n) for indexed binary heap
     *                  O(1) amortized for Fibonacci heap
     */
    decreaseKey?(element: T, newPriority: number): void;
    
    /**
     * Removes a specific element from the queue (not necessarily the minimum).
     * 
     * @param element - The element to remove
     * @returns true if element was found and removed, false otherwise
     * 
     * Time Complexity: O(n) for basic heap (find) + O(log n) for removal
     *                  O(log n) for indexed heap
     */
    remove?(element: T): boolean;
    
    /**
     * Checks whether a specific element exists in the queue.
     * 
     * @param element - The element to search for
     * @returns true if element is in the queue, false otherwise
     * 
     * Time Complexity: O(n) for basic heap, O(1) for indexed heap
     */
    contains?(element: T): boolean;
    
    /**
     * Removes all elements from the priority queue.
     * 
     * Time Complexity: O(1) or O(n) depending on memory management
     */
    clear?(): void;
}

The Insert Operation

The insert operation (also called push, enqueue, or add in various libraries) is the primary way to add elements to a priority queue. Let's examine it comprehensively.

Operation Semantics:

insert(element: T, priority: P) → void

Preconditions:

The priority value must be comparable (typically numeric)
Element may or may not be required to be unique (implementation-dependent)
Queue has capacity (for bounded implementations)

Postconditions:

Element is now in the queue
Queue size increased by 1
The heap invariant is maintained
The element will be returned by extractMin when no lower-priority elements exist

Insert Operation Details

•Time Complexity — O(log n) for binary heaps. The element is added at the end and 'bubbles up' to its correct position, visiting at most log₂(n) levels.
•Space Complexity — O(1) additional space (the element is stored, but no auxiliary structures needed for the operation itself).
•Duplicate Handling — Most priority queues allow duplicates. If you insert the same element twice, it exists twice with potentially different priorities.
•Priority Coupling — Some APIs couple element and priority (insert(element, priority)), others expect comparable elements where priority is inherent (insert(comparableElement)).

insert-operation-examples
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Example 1: Basic insert with explicit priority
const taskQueue = new PriorityQueue<string>();
 
taskQueue.insert("Email notification", 5);    // Low priority (5)
taskQueue.insert("Security alert", 1);        // High priority (1)
taskQueue.insert("Database backup", 3);       // Medium priority (3)
 
// Queue state: Security alert will be extracted first
 
// Example 2: Insert with derived priority
interface ScheduledTask {
    name: string;
    deadline: Date;
}
 
const scheduler = new PriorityQueue<ScheduledTask>();
 
const task1: ScheduledTask = {
    name: "Submit report",
    deadline: new Date("2024-01-15")
};
 
// Priority is the deadline timestamp (earlier = more urgent)
scheduler.insert(task1, task1.deadline.getTime());
 
// Example 3: Handling insert edge cases
function safeInsert<T>(
    queue: PriorityQueue<T>,
    element: T,
    priority: number
): boolean {
    // Validate priority
    if (!Number.isFinite(priority)) {
        console.error("Priority must be a finite number");
        return false;
    }
    
    // Check for NaN
    if (Number.isNaN(priority)) {
        console.error("Priority cannot be NaN");
        return false;
    }
    
    try {
        queue.insert(element, priority);
        return true;
    } catch (error) {
        console.error("Insert failed:", error);
        return false;
    }
}

Mutable Priority Pitfall

The Extract Operation

Operation Semantics:

extractMin() → T    // For min-priority queue
extractMax() → T    // For max-priority queue

Alternative Names:

poll() (Java)
heappop() (Python's heapq)
pop() or top() combined with removal
dequeue() (drawing parallel to standard queues)

Extract Operation Details

•Time Complexity — O(log n) for binary heaps. After removing the root, the last element takes its place and 'bubbles down' to restore the heap property.
•Empty Queue Behavior — Critical design decision! Options: throw exception, return null/undefined, return Optional/Maybe. Know your library's convention.
•Destructive Operation — Unlike peek, extract modifies the queue. The element is gone after extraction. If you need to re-examine, use peek first.
•Tie-Breaking — When multiple elements share the minimum priority, which one is returned? Implementation-dependent. Stable queues return the earliest inserted.

extract-operation-examples
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Safe extraction patterns
 
class SafePriorityQueue<T> {
    private heap: Array<{ element: T; priority: number }> = [];
    
    /**
     * Extract minimum - throws on empty queue
     * Use when: empty queue is a programming error
     */
    extractMin(): T {
        if (this.isEmpty()) {
            throw new Error("Cannot extract from empty priority queue");
        }
        return this.doExtract();
    }
    
    /**
     * Try extract - returns undefined on empty queue
     * Use when: empty queue is a normal condition
     */
    tryExtractMin(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.doExtract();
    }
    
    /**
     * Extract with result wrapper
     * Use when: you want explicit success/failure handling
     */
    extractMinResult(): { success: true; value: T } | { success: false } {
        if (this.isEmpty()) {
            return { success: false };
        }
        return { success: true, value: this.doExtract() };
    }
    
    private doExtract(): T {
        const min = this.heap[0].element;
        const last = this.heap.pop()!;
        
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        
        return min;
    }
    
    isEmpty(): boolean {
        return this.heap.length === 0;
    }
    
    private bubbleDown(index: number): void {
        // Implementation details...
    }
}
 
// Usage patterns
const pq = new SafePriorityQueue<string>();
pq.insert("task1", 1);
pq.insert("task2", 2);
 
// Pattern 1: Check then extract (two operations, potential race condition)
if (!pq.isEmpty()) {
    const task = pq.extractMin();
    processTask(task);
}
 
// Pattern 2: Try extract (single operation, null check required)
const maybeTask = pq.tryExtractMin();
if (maybeTask !== undefined) {
    processTask(maybeTask);
}
 
// Pattern 3: Extract until empty (common loop pattern)
while (!pq.isEmpty()) {
    const task = pq.extractMin();
    processTask(task);
}
 
// Pattern 4: Process N items or until empty
function processUpToN<T>(queue: SafePriorityQueue<T>, n: number): T[] {
    const results: T[] = [];
    for (let i = 0; i < n && !queue.isEmpty(); i++) {
        results.push(queue.extractMin());
    }
    return results;
}
 
function processTask(task: string): void {
    console.log(`Processing: ${task}`);
}

Extraction Order is the Output

The Peek Operation

Operation Semantics:

peek() → T    // Returns minimum/maximum without removal

Why Peek Matters:

Peek enables important patterns:

Conditional Processing — Examine the next item before deciding whether to process it
Threshold Checking — Is the top priority above/below a threshold?
Monitoring — Report what's coming next without affecting the queue
Algorithm Correctness — Some algorithms need to inspect without extracting

Peek Operation Details

•Time Complexity — O(1). The minimum/maximum is always at the root (index 0 for array-based heaps). No traversal needed.
•Non-Destructive — The queue state is unchanged. Calling peek multiple times returns the same element.
•Empty Queue Handling — Same considerations as extract. Throw, return null, or use Optional wrapper.
•Reference vs Value — Peek typically returns a reference to the actual element. Modifying it (especially priority-related fields) can corrupt the heap!

peek-operation-examples
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
interface Task {
    id: string;
    priority: number;
    deadline: Date;
}
 
class TaskScheduler {
    private queue: PriorityQueue<Task>;
    private currentTime: Date;
    
    constructor() {
        this.queue = new PriorityQueue<Task>();
        this.currentTime = new Date();
    }
    
    /**
     * Pattern 1: Conditional processing based on peek
     * Only process if the top task is ready
     */
    processIfReady(): Task | null {
        if (this.queue.isEmpty()) {
            return null;
        }
        
        const nextTask = this.queue.peek();
        
        // Check if task is ready to be processed
        if (nextTask.deadline <= this.currentTime) {
            // Deadline has passed, process immediately
            return this.queue.extractMin();
        }
        
        // Not ready yet, don't extract
        return null;
    }
    
    /**
     * Pattern 2: Batch processing with priority threshold
     * Process all high-priority items (priority < threshold)
     */
    processHighPriority(threshold: number): Task[] {
        const processed: Task[] = [];
        
        // Keep processing while queue has items below threshold
        while (!this.queue.isEmpty() && 
               this.queue.peek().priority < threshold) {
            processed.push(this.queue.extractMin());
        }
        
        return processed;
    }
    
    /**
     * Pattern 3: Time-until-next calculation
     * How long until the next task is due?
     */
    timeUntilNext(): number | null {
        if (this.queue.isEmpty()) {
            return null;  // No tasks pending
        }
        
        const nextTask = this.queue.peek();
        const msUntilDeadline = nextTask.deadline.getTime() - 
                                this.currentTime.getTime();
        
        return Math.max(0, msUntilDeadline);
    }
    
    /**
     * Pattern 4: Peek for logging/monitoring
     */
    logQueueStatus(): void {
        if (this.queue.isEmpty()) {
            console.log("Queue is empty");
            return;
        }
        
        const top = this.queue.peek();
        console.log(`Queue size: ${this.queue.size()}`);
        console.log(`Next task: ${top.id} (priority ${top.priority})`);
        console.log(`Due: ${top.deadline.toISOString()}`);
        // Queue unchanged after logging
    }
}

Peek and Immutability

The isEmpty and Size Operations

While less glamorous than insert and extract, the isEmpty and size operations are essential for control flow and handling edge cases. Let's examine them with the rigor they deserve.

isEmpty Operation:

isEmpty() → boolean

size Operation:

size() → integer

Both are O(1) operations in all reasonable implementations—the size is tracked as elements are inserted and extracted.

Why Two Operations?

You might ask: "Why have isEmpty when we can just check size() === 0?" Several reasons:

Reasons for Separate isEmpty

•Semantic Clarity — isEmpty() clearly expresses intent. size() === 0 requires the reader to parse an equality check.
•Potential Optimization — For some data structures, checking emptiness can be faster than computing full size. (Not relevant for heaps, but matters for consistency across ADTs.)
•Null/Undefined Safety — isEmpty() returns a definite boolean. size() returns a number that must be compared.
•Convention — Most collection APIs include isEmpty. Consistency aids learnability.

isempty-size-patterns
TypeScript
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Common patterns using isEmpty and size
 
function drainQueue<T>(queue: PriorityQueue<T>): T[] {
    const results: T[] = [];
    
    while (!queue.isEmpty()) {
        results.push(queue.extractMin());
    }
    
    return results;
}
 
function processWithLimit<T>(
    queue: PriorityQueue<T>,
    maxItems: number
): T[] {
    const results: T[] = [];
    
    // Use size for limiting, isEmpty for existence check
    const toProcess = Math.min(maxItems, queue.size());
    
    for (let i = 0; i < toProcess; i++) {
        results.push(queue.extractMin());
    }
    
    return results;
}
 
function reportQueueHealth<T>(queue: PriorityQueue<T>): string {
    if (queue.isEmpty()) {
        return "Queue is empty - no pending work";
    }
    
    const size = queue.size();
    
    if (size < 10) {
        return `Queue healthy: ${size} items`;
    } else if (size < 100) {
        return `Queue growing: ${size} items - consider scaling`;
    } else {
        return `Queue critical: ${size} items - immediate attention needed`;
    }
}
 
// Pattern: Guard clause with isEmpty
function processNext<T>(queue: PriorityQueue<T>): T | null {
    if (queue.isEmpty()) {
        return null;  // Early return for empty queue
    }
    
    return queue.extractMin();
}
 
// Pattern: Batch size calculation
function calculateBatchSize<T>(
    queue: PriorityQueue<T>,
    preferredBatch: number
): number {
    // Take preferred batch size or remaining items, whichever is smaller
    return Math.min(preferredBatch, queue.size());
}
 
// Pattern: Progress reporting
function processWithProgress<T>(
    queue: PriorityQueue<T>,
    process: (item: T) => void
): void {
    const total = queue.size();
    let processed = 0;
    
    while (!queue.isEmpty()) {
        process(queue.extractMin());
        processed++;
        
        // Report progress every 10%
        if (processed % Math.ceil(total / 10) === 0) {
            console.log(`Progress: ${processed}/${total} (${
                Math.round(processed / total * 100)
            }%)`);
        }
    }
    
    console.log("Processing complete!");
}

Concurrency Warning

Extended Operations: decreaseKey, remove, contains

Beyond the core operations, many priority queue implementations offer extended operations that enable more sophisticated use cases. These are often crucial for specific algorithms.

decreaseKey (or increasePriority):

This operation lowers the priority value of an existing element (which, in a min-heap, means it becomes more important). It's essential for algorithms like Dijkstra's shortest path.

decreaseKey(element, newPriority) → void

Time Complexity:

O(n) for basic heap (must find element first)
O(log n) for indexed heap (direct lookup via auxiliary map)

extended-operations
TypeScript
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**
 * Indexed Priority Queue with full extended operations
 */
class IndexedPriorityQueue<K, V> {
    private heap: Array<{ key: K; value: V; priority: number }> = [];
    private keyToIndex: Map<K, number> = new Map();
    
    // Core operations...
    insert(key: K, value: V, priority: number): void { /* ... */ }
    extractMin(): { key: K; value: V; priority: number } | undefined { /* ... */ }
    peek(): { key: K; value: V; priority: number } | undefined { /* ... */ }
    isEmpty(): boolean { return this.heap.length === 0; }
    size(): number { return this.heap.length; }
    
    /**
     * Decrease the priority of an existing element.
     * Critical for Dijkstra's algorithm.
     * 
     * @throws Error if key not found or new priority is not lower
     */
    decreaseKey(key: K, newPriority: number): void {
        const index = this.keyToIndex.get(key);
        
        if (index === undefined) {
            throw new Error(`Key not found: ${String(key)}`);
        }
        
        const currentPriority = this.heap[index].priority;
        
        if (newPriority >= currentPriority) {
            throw new Error(
                `New priority (${newPriority}) must be less than ` +
                                        `current (${currentPriority})`
            );
        }
        
        this.heap[index].priority = newPriority;
        this.bubbleUp(index);  // Priority improved, might need to rise
    }
    
    /**
     * Increase the priority of an existing element.
     * Less common, but useful for aging or demotion.
     */
    increaseKey(key: K, newPriority: number): void {
        const index = this.keyToIndex.get(key);
        
        if (index === undefined) {
            throw new Error(`Key not found: ${String(key)}`);
        }
        
        const currentPriority = this.heap[index].priority;
        
        if (newPriority <= currentPriority) {
            throw new Error(
                `New priority (${newPriority}) must be greater than current (${currentPriority})`
            );
        }
        
        this.heap[index].priority = newPriority;
        this.bubbleDown(index);  // Priority worsened, might need to sink
    }
    
    /**
     * Check if a key exists in the queue.
     */
    contains(key: K): boolean {
        return this.keyToIndex.has(key);
    }
    
    /**
     * Remove an arbitrary element (not just the minimum).
     */
    remove(key: K): boolean {
        const index = this.keyToIndex.get(key);
        
        if (index === undefined) {
            return false;  // Key not found
        }
        
        // Strategy: decrease key to -Infinity, then extract
        // This is cleaner than handling the general remove case
        this.heap[index].priority = Number.NEGATIVE_INFINITY;
        this.bubbleUp(index);  // Now at root
        this.extractMin();     // Remove it
        
        return true;
    }
    
    /**
     * Get the current priority of a key.
     */
    getPriority(key: K): number | undefined {
        const index = this.keyToIndex.get(key);
        return index !== undefined ? this.heap[index].priority : undefined;
    }
    
    /**
     * Insert or update: if key exists, update priority; else insert.
     */
    upsert(key: K, value: V, priority: number): void {
        if (this.contains(key)) {
            const currentPriority = this.getPriority(key)!;
            if (priority < currentPriority) {
                this.decreaseKey(key, priority);
            } else if (priority > currentPriority) {
                this.increaseKey(key, priority);
            }
            // If equal, nothing to do
        } else {
            this.insert(key, value, priority);
        }
    }
    
    // Helper methods for heap maintenance
    private bubbleUp(index: number): void { /* ... */ }
    private bubbleDown(index: number): void { /* ... */ }
    private swap(i: number, j: number): void { /* ... */ }
}

Dijkstra's Algorithm — Why decreaseKey Matters:

In Dijkstra's shortest path algorithm, when we find a shorter path to a vertex, we need to update its tentative distance in the priority queue. Without decreaseKey:

Option 1: Insert duplicates and ignore stale entries (memory wasteful)
Option 2: Remove and re-insert (O(n) to find for basic heap)

With decreaseKey in an indexed heap:

O(log n) priority update directly
No duplicates needed
Clean, efficient implementation

This is why indexed priority queues (where we can look up elements by key in O(1)) are used for graph algorithms.

Library Support Varies

Priority Queues in Standard Libraries

Different programming languages provide different APIs for priority queues. Understanding these variations helps you work effectively across languages and choose appropriate implementations.

Key Differences to Watch:

Min-heap vs max-heap default
Naming conventions (add vs insert vs push)
Error handling (exceptions vs null)
Support for extended operations

Priority Queue APIs Across Languages
Language	Class/Module	Default Order	Insert	Extract	Peek
Python	heapq	Min-heap	heappush(h, x)	heappop(h)	h[0]
Java	PriorityQueue	Min-heap	add(e) / offer(e)	poll() / remove()	peek()
C++	priority_queue	Max-heap	push(x)	pop() + top()	top()
C#	PriorityQueue<T,P>	Min-heap	Enqueue(e, p)	Dequeue()	Peek()
Go	container/heap	Min-heap*	Push(h, x)	Pop(h)	h[0] / (*h)[0]
Rust	BinaryHeap	Max-heap	push(x)	pop()	peek()

language-comparison
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
32
33
34
35
36
37
38
39
40
41
// JavaScript/TypeScript has NO built-in priority queue!
// Common options:
// 1. Implement your own
// 2. Use a library (e.g., @datastructures-js/priority-queue)
 
// Example with @datastructures-js/priority-queue
import { 
    MinPriorityQueue, 
    MaxPriorityQueue 
} from '@datastructures-js/priority-queue';
 
// Min priority queue (number elements)
const minQueue = new MinPriorityQueue<number>();
minQueue.enqueue(5);
minQueue.enqueue(2);
minQueue.enqueue(8);
 
console.log(minQueue.dequeue()); // { priority: 2, element: 2 }
console.log(minQueue.front());   // { priority: 5, element: 5 }
 
// With custom priority function
const taskQueue = new MinPriorityQueue<Task>(task => task.priority);
taskQueue.enqueue({ id: "1", priority: 5 });
taskQueue.enqueue({ id: "2", priority: 2 });
 
// Simple array-based implementation for quick needs
class SimplePQ<T> {
    private items: Array<{ element: T; priority: number }> = [];
    
    enqueue(element: T, priority: number): void {
        this.items.push({ element, priority });
        this.items.sort((a, b) => a.priority - b.priority);
    }
    
    dequeue(): T | undefined {
        return this.items.shift()?.element;
    }
    
    // Note: O(n log n) insert due to sorting - not efficient!
    // Use proper heap for production
}

C++ Gotcha: pop() Doesn't Return

Summary: The Priority Queue Interface

We've comprehensively covered the priority queue interface—the operations that define this abstract data type regardless of implementation. Let's consolidate our understanding.

Key Takeaways

•Core operations are minimal — insert, extractMin/Max, peek, isEmpty, size. This small interface provides enormous power.
•insert is O(log n) — Elements bubble up to their correct position, visiting at most log₂(n) levels.
•extractMin is O(log n) — The replacement element bubbles down, restoring the heap property.
•peek is O(1) — The extreme element is always at the root, accessible instantly.
•Extended operations enable algorithms — decreaseKey is crucial for Dijkstra's; contains and remove support more flexible usage.
•Error handling varies — Know whether your library throws, returns null, or uses Optional for empty-queue operations.
•Standard libraries differ significantly — Default ordering (min vs max), method names, and supported operations vary by language.

What's Next:

Page Complete