Chapter 13: Heaps and Priority Queues: Efficient Prioritization

Welcome back, intrepid coder! In our journey through Data Structures and Algorithms, we’ve explored linear structures like arrays and linked lists, and delved into the hierarchical world of trees. Now, we’re about to meet a special type of tree-based structure that’s all about efficiency when it comes to prioritizing elements: Heaps and their powerful application, Priority Queues.

This chapter will unravel the mysteries of Heaps, explain how they maintain a specific order, and show you how they form the backbone of a Priority Queue. You’ll learn not just what they are, but why they’re incredibly useful in various real-world scenarios, from operating system task scheduling to finding the shortest path in a navigation app. By the end, you’ll have a solid conceptual understanding and a hands-on TypeScript implementation of a Priority Queue. Get ready to add another powerful tool to your DSA toolkit!

What is a Heap? The Secret to Efficient Prioritization

Imagine you’re managing a bustling hospital emergency room. Patients arrive, but they can’t all be seen in the order they walk through the door. Some need immediate attention (critical), others can wait a bit (urgent), and some are non-emergency. You need a system to always know who the most critical patient is, so they can be treated next. This is exactly the kind of problem a Heap helps solve!

A Heap is a specialized tree-based data structure that satisfies the heap property. While it’s conceptually a tree, it’s almost always implemented using an array, making it very memory-efficient.

There are two main types of heaps:

1. Min-Heap: In a Min-Heap, the value of each node is less than or equal to the value of its children. This means the smallest element is always at the root. Think of it like a strict family where the youngest (smallest value) always gets the top spot.
2. Max-Heap: In a Max-Heap, the value of each node is greater than or equal to the value of its children. This means the largest element is always at the root. Here, the oldest (largest value) rules the roost.

Let’s break down the two critical properties that define a binary heap:

1. The Shape Property: A Complete Binary Tree

A heap must always be a complete binary tree. What does that mean?

• Every level, except possibly the last, is completely filled.
• All nodes in the last level are as far left as possible.

This “completeness” is crucial because it allows us to represent the tree efficiently using a simple array, without any gaps.

2. The Heap Property: Ordering Matters

As mentioned, this property dictates the relationship between a parent node and its children.

• Min-Heap Property: parent.value <= child.value
• Max-Heap Property: parent.value >= child.value

Take a moment to ponder: Why is having the smallest (or largest) element always at the root so powerful? Think about how quickly you could retrieve that element!

Array Representation of a Heap

This is where heaps get clever. Because they are complete binary trees, we can map them perfectly onto an array.

• The root is at index 0.
• For any node at index i:
  • Its left child is at index 2 * i + 1.
  • Its right child is at index 2 * i + 2.
  • Its parent is at index Math.floor((i - 1) / 2).

Let’s visualize this with a small Min-Heap:

In this example:

• Node 1 (index 0) has children 3 (index 1) and 5 (index 2).
• Node 3 (index 1) has children 7 (index 3) and 8 (index 4).
• Node 5 (index 2) has child 10 (index 5).

Notice how the smallest element, 1, is at the root (index 0). This is the magic of the Min-Heap!

What is a Priority Queue? The Application

A Priority Queue is an Abstract Data Type (ADT), meaning it defines a set of operations without specifying how those operations are implemented. It’s like a regular queue, but with a twist: each element has an associated “priority.” When you dequeue an element, you don’t get the one that’s been waiting the longest (FIFO); instead, you get the one with the highest priority.

Think of the emergency room again. Patients are added to a queue, but the one with the highest priority (most critical condition) is always seen next, regardless of when they arrived.

The core operations of a Priority Queue are:

• insert(element, priority): Adds an element with its priority to the queue.
• extractMin() or extractMax(): Removes and returns the element with the highest (or lowest, depending on implementation) priority.
• peek(): Returns the element with the highest priority without removing it.
• isEmpty(): Checks if the queue is empty.
• size(): Returns the number of elements in the queue.

While a Priority Queue could be implemented with an unsorted array (O(N) for extractMin/Max) or a sorted array (O(N) for insert), a Heap is the most efficient and common way to implement a Priority Queue. Why? Because a Heap allows insert and extractMin/Max operations in O(log N) time! This logarithmic time complexity makes Heaps incredibly performant for large datasets.

Now that we understand the theory, let’s roll up our sleeves and implement a Min-Priority Queue using a Min-Heap in TypeScript. We’ll prioritize elements by their numerical value (smallest value = highest priority).

Step-by-Step Implementation: Building a Min-Priority Queue

We’ll create a MinPriorityQueue class that uses an array to store its heap elements. For simplicity, our elements will just be numbers, where smaller numbers have higher priority.

Let’s start by setting up our project. If you’ve been following along, you should already have Node.js and TypeScript installed. We’ll use Node.js v24.13.0 LTS as of 2026-02-16, which is a stable and recommended version. TypeScript v5.x is the current major stable release.

Create a new directory for this chapter, navigate into it, and initialize a tsconfig.json if you haven’t already:

mkdir chapter13-heaps
cd chapter13-heaps
npm init -y
npm install typescript@latest node@latest --save-dev # Install latest stable TypeScript and Node.js types
npx tsc --init # Initialize tsconfig.json

Open tsconfig.json and ensure outDir is set to ./dist and rootDir to ./src. Also, make sure target is es2022 or esnext and module is commonjs or esnext.

Now, create a src folder and an index.ts file inside it: src/index.ts.

1. The MinPriorityQueue Class Structure

We’ll start with the basic class and an array to hold our heap elements.

// src/index.ts

/**
 * Represents a Min-Priority Queue implemented using a Min-Heap.
 * Smaller numbers have higher priority.
 */
class MinPriorityQueue {
    // The heap array where elements are stored.
    // We use a simple array and rely on the heap property for ordering.
    private heap: number[] = [];

    constructor() {}

    /**
     * Returns the current number of elements in the priority queue.
     * @returns The size of the queue.
     */
    size(): number {
        return this.heap.length;
    }

    /**
     * Checks if the priority queue is empty.
     * @returns True if empty, false otherwise.
     */
    isEmpty(): boolean {
        return this.size() === 0;
    }
}

Explanation:

• We declare a private heap array of numbers (number[]). This array will store our heap elements.
• The constructor is empty for now, as the heap is initialized directly.
• size() and isEmpty() are straightforward helper methods to check the state of our queue.

2. Essential Helper Methods for Heap Navigation

To manage the heap efficiently, we need functions to calculate parent and child indices and to swap elements.

// src/index.ts (add these inside the MinPriorityQueue class)

// ... (previous code for class, constructor, size, isEmpty)

    // Helper methods for calculating indices
    private getParentIndex(i: number): number {
        return Math.floor((i - 1) / 2);
    }

    private getLeftChildIndex(i: number): number {
        return 2 * i + 1;
    }

    private getRightChildIndex(i: number): number {
        return 2 * i + 2;
    }

    // Helper methods to check if a node has parent/children
    private hasParent(i: number): boolean {
        return this.getParentIndex(i) >= 0;
    }

    private hasLeftChild(i: number): boolean {
        return this.getLeftChildIndex(i) < this.size();
    }

    private hasRightChild(i: number): boolean {
        return this.getRightChildIndex(i) < this.size();
    }

    // Helper methods to get parent/child values
    private getParent(i: number): number {
        return this.heap[this.getParentIndex(i)];
    }

    private getLeftChild(i: number): number {
        return this.heap[this.getLeftChildIndex(i)];
    }

    private getRightChild(i: number): number {
        return this.heap[this.getRightChildIndex(i)];
    }

    // Helper method to swap two elements in the heap array
    private swap(indexOne: number, indexTwo: number): void {
        const temp = this.heap[indexOne];
        this.heap[indexOne] = this.heap[indexTwo];
        this.heap[indexTwo] = temp;
    }
}

Explanation:

• getParentIndex, getLeftChildIndex, getRightChildIndex: These implement the array-to-tree index mapping we discussed. Math.floor is crucial for parent index to handle both left and right children correctly.
• hasParent, hasLeftChild, hasRightChild: These check array bounds to prevent errors when accessing non-existent nodes.
• getParent, getLeftChild, getRightChild: These simply retrieve the value at the calculated index.
• swap: A standard utility function to exchange elements at two given indices in the heap array.

3. peek(): Looking at the Highest Priority Item

This is the easiest operation. In a Min-Heap, the highest priority item (smallest value) is always at the root (index 0).

// src/index.ts (add this inside the MinPriorityQueue class)

// ... (previous helper methods)

    /**
     * Returns the element with the highest priority (smallest value) without removing it.
     * Throws an error if the queue is empty.
     * @returns The highest priority element.
     */
    peek(): number {
        if (this.isEmpty()) {
            throw new Error("Priority queue is empty.");
        }
        return this.heap[0];
    }
}

Explanation:

• We first check if the queue is empty to avoid errors.
• If not empty, we simply return the element at heap[0].
• Time Complexity: O(1) – constant time, super fast!

4. insert(): Adding Elements and Maintaining the Heap

When we add a new element, we initially place it at the very end of our heap array. This maintains the “complete binary tree” (shape) property. However, it might violate the “heap property” if the new element is smaller than its parent (in a Min-Heap). To fix this, we perform a process called heapifyUp (or “bubble up”).

// src/index.ts (add these inside the MinPriorityQueue class)

// ... (previous peek method)

    /**
     * Adds a new element to the priority queue.
     * @param element The number to add.
     */
    insert(element: number): void {
        this.heap.push(element); // Add to the end
        this.heapifyUp();        // Restore heap property by bubbling up
    }

    // Restores the heap property by moving the last element up the tree
    // until its parent is smaller or it reaches the root.
    private heapifyUp(): void {
        let currentIndex = this.size() - 1; // Start from the newly added element

        // While the current node has a parent AND the current node is smaller than its parent
        while (this.hasParent(currentIndex) && this.getParent(currentIndex) > this.heap[currentIndex]) {
            // Swap the current node with its parent
            this.swap(currentIndex, this.getParentIndex(currentIndex));
            // Move up to the parent's position
            currentIndex = this.getParentIndex(currentIndex);
        }
    }
}

Explanation:

• insert(element):
  1. this.heap.push(element): We add the new element to the end of the heap array. This keeps the tree “complete.”
  2. this.heapifyUp(): We then call heapifyUp to put the new element in its correct sorted position within the heap.
• heapifyUp():
  1. currentIndex starts at the index of the newly added element (the last element).
  2. The while loop continues as long as two conditions are met:
     • The currentIndex has a parent (it’s not the root).
     • The current element is smaller than its parent (violating the Min-Heap property).
  3. Inside the loop, we swap the current element with its parent.
  4. Then, currentIndex is updated to the parent’s index, effectively moving “up” the tree.
  5. This process continues until the element is either at the root or its parent is smaller than it, satisfying the Min-Heap property.

Time Complexity for insert(): In the worst case, the new element might need to bubble up all the way to the root. The height of a complete binary tree with N nodes is log N. So, insert() takes O(log N) time.

5. extractMin(): Removing the Highest Priority Item

Removing the highest priority element (the smallest one in a Min-Heap) is a bit more involved.

1. The root (heap[0]) is the element we want to remove.
2. To maintain the “complete binary tree” property, we move the last element of the heap to the root’s position.
3. We then remove the last element from the array.
4. Now, the new root might violate the heap property (it’s likely larger than its children). We fix this by performing a process called heapifyDown (or “bubble down”).

// src/index.ts (add these inside the MinPriorityQueue class)

// ... (previous insert method)

    /**
     * Removes and returns the element with the highest priority (smallest value).
     * Throws an error if the queue is empty.
     * @returns The highest priority element.
     */
    extractMin(): number {
        if (this.isEmpty()) {
            throw new Error("Priority queue is empty.");
        }
        if (this.size() === 1) {
            return this.heap.pop()!; // Simply remove and return the only element
        }

        const min = this.heap[0]; // The smallest element is at the root
        this.heap[0] = this.heap.pop()!; // Move the last element to the root
        this.heapifyDown();              // Restore heap property by bubbling down

        return min;
    }

    // Restores the heap property by moving the root element down the tree
    // until its children are larger or it becomes a leaf.
    private heapifyDown(): void {
        let currentIndex = 0; // Start from the root (the element that was just moved there)

        // While the current node has at least one left child (meaning it might have children)
        while (this.hasLeftChild(currentIndex)) {
            let smallerChildIndex = this.getLeftChildIndex(currentIndex); // Assume left child is smaller

            // If there's a right child AND the right child is smaller than the left child,
            // then the right child is the true smaller child.
            if (this.hasRightChild(currentIndex) && this.getRightChild(currentIndex) < this.getLeftChild(currentIndex)) {
                smallerChildIndex = this.getRightChildIndex(currentIndex);
            }

            // If the current node is already smaller than or equal to its smallest child,
            // then the heap property is satisfied, and we can stop.
            if (this.heap[currentIndex] <= this.heap[smallerChildIndex]) {
                break;
            } else {
                // Otherwise, swap the current node with its smaller child
                this.swap(currentIndex, smallerChildIndex);
                // Move down to the smaller child's position
                currentIndex = smallerChildIndex;
            }
        }
    }
}

Explanation:

• extractMin():
  1. Handles empty queue and single-element queue edge cases.
  2. min = this.heap[0]: We store the root (the smallest element).
  3. this.heap[0] = this.heap.pop()!: The last element is moved to the root, and the original last element is removed from the array. ! is a non-null assertion, safe here because we’ve handled isEmpty and size() === 1.
  4. this.heapifyDown(): We call heapifyDown to put the new root in its correct sorted position.
  5. return min: The original smallest element is returned.
• heapifyDown():
  1. currentIndex starts at the root (index 0).
  2. The while loop continues as long as the current node hasLeftChild. If it has a left child, it might have a right child too, and thus might need to move down.
  3. smallerChildIndex is determined by comparing the left and right children. We want to swap with the smaller of the two children to maintain the Min-Heap property.
  4. If the currentIndex element is already smaller than or equal to smallerChildIndex element, the heap property is satisfied, and we break.
  5. Otherwise, we swap the current element with the smallerChildIndex element.
  6. currentIndex is updated to smallerChildIndex, moving “down” the tree.
  7. This process continues until the element is in its correct place or becomes a leaf.

Time Complexity for extractMin(): Similar to insert(), in the worst case, the element moved to the root might need to bubble down all the way to a leaf. This also takes O(log N) time.

6. Putting It All Together and Testing

Let’s add some usage examples to src/index.ts.

// src/index.ts (Complete code)

/**
 * Represents a Min-Priority Queue implemented using a Min-Heap.
 * Smaller numbers have higher priority.
 */
class MinPriorityQueue {
    private heap: number[] = [];

    constructor() {}

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.size() === 0;
    }

    private getParentIndex(i: number): number {
        return Math.floor((i - 1) / 2);
    }

    private getLeftChildIndex(i: number): number {
        return 2 * i + 1;
    }

    private getRightChildIndex(i: number): number {
        return 2 * i + 2;
    }

    private hasParent(i: number): boolean {
        return this.getParentIndex(i) >= 0;
    }

    private hasLeftChild(i: number): boolean {
        return this.getLeftChildIndex(i) < this.size();
    }

    private hasRightChild(i: number): boolean {
        return this.getRightChildIndex(i) < this.size();
    }

    private getParent(i: number): number {
        return this.heap[this.getParentIndex(i)];
    }

    private getLeftChild(i: number): number {
        return this.heap[this.getLeftChildIndex(i)];
    }

    private getRightChild(i: number): number {
        return this.heap[this.getRightChildIndex(i)];
    }

    private swap(indexOne: number, indexTwo: number): void {
        const temp = this.heap[indexOne];
        this.heap[indexOne] = this.heap[indexTwo];
        this.heap[indexTwo] = temp;
    }

    peek(): number {
        if (this.isEmpty()) {
            throw new Error("Priority queue is empty.");
        }
        return this.heap[0];
    }

    insert(element: number): void {
        this.heap.push(element);
        this.heapifyUp();
    }

    private heapifyUp(): void {
        let currentIndex = this.size() - 1;
        while (this.hasParent(currentIndex) && this.getParent(currentIndex) > this.heap[currentIndex]) {
            this.swap(currentIndex, this.getParentIndex(currentIndex));
            currentIndex = this.getParentIndex(currentIndex);
        }
    }

    extractMin(): number {
        if (this.isEmpty()) {
            throw new Error("Priority queue is empty.");
        }
        if (this.size() === 1) {
            return this.heap.pop()!;
        }

        const min = this.heap[0];
        this.heap[0] = this.heap.pop()!;
        this.heapifyDown();

        return min;
    }

    private heapifyDown(): void {
        let currentIndex = 0;
        while (this.hasLeftChild(currentIndex)) {
            let smallerChildIndex = this.getLeftChildIndex(currentIndex);
            if (this.hasRightChild(currentIndex) && this.getRightChild(currentIndex) < this.getLeftChild(currentIndex)) {
                smallerChildIndex = this.getRightChildIndex(currentIndex);
            }

            if (this.heap[currentIndex] <= this.heap[smallerChildIndex]) {
                break;
            } else {
                this.swap(currentIndex, smallerChildIndex);
                currentIndex = smallerChildIndex;
            }
        }
    }
}

// --- Let's test our MinPriorityQueue! ---
console.log("--- Initializing MinPriorityQueue ---");
const pq = new MinPriorityQueue();
console.log(`Is empty? ${pq.isEmpty()}`); // Expected: true

console.log("\n--- Inserting elements ---");
pq.insert(10);
pq.insert(5);
pq.insert(15);
pq.insert(2);
pq.insert(8);
pq.insert(12);

console.log(`Queue size: ${pq.size()}`); // Expected: 6
console.log(`Highest priority (peek): ${pq.peek()}`); // Expected: 2 (smallest value)

console.log("\n--- Extracting elements ---");
console.log(`Extracted: ${pq.extractMin()}`); // Expected: 2
console.log(`Current highest priority: ${pq.peek()}`); // Expected: 5

console.log(`Extracted: ${pq.extractMin()}`); // Expected: 5
console.log(`Current highest priority: ${pq.peek()}`); // Expected: 8

pq.insert(1); // Insert a new highest priority item
console.log(`Inserted 1. Current highest priority: ${pq.peek()}`); // Expected: 1

while (!pq.isEmpty()) {
    console.log(`Extracted: ${pq.extractMin()}`);
}
console.log(`Is empty after all extractions? ${pq.isEmpty()}`); // Expected: true

try {
    pq.peek();
} catch (error: any) {
    console.log(`Error on peek when empty: ${error.message}`); // Expected: "Priority queue is empty."
}

To run this code:

1. Save the complete code in src/index.ts.
2. Compile the TypeScript: npx tsc
3. Run the compiled JavaScript: node dist/index.js

You should see output demonstrating the correct behavior of the Min-Priority Queue, always extracting the smallest element first!

Mini-Challenge: Build a Max-Priority Queue

You’ve successfully built a Min-Priority Queue. Now, it’s your turn to apply what you’ve learned to create its counterpart!

Challenge: Implement a MaxPriorityQueue class. This class should also use a heap, but this time, the largest number should always have the highest priority (and thus be at the root).

Hints:

1. You’ll need to adjust the comparison logic in heapifyUp and heapifyDown. Instead of > for getParent(currentIndex) > this.heap[currentIndex], what should it be for a Max-Heap?
2. Similarly, when finding the “better” child in heapifyDown, you’ll be looking for the larger child, not the smaller one.
3. The main extraction method will be extractMax().
4. The peek() method will still return this.heap[0], but now it represents the maximum value.

Take your time, review the MinPriorityQueue logic, and think about how the comparisons need to flip. This is a fantastic way to solidify your understanding of heap properties!

Common Pitfalls & Troubleshooting

1. Off-by-One Errors in Index Calculations: The most common mistake in heap implementations. Double-check 2*i+1, 2*i+2, and Math.floor((i-1)/2). Remember that Math.floor is crucial for getParentIndex to work correctly for both left and right children.
2. Incorrect Comparison Logic: For a Min-Heap, a parent must be less than or equal to its children. For a Max-Heap, a parent must be greater than or equal to its children. Mixing these up will break the heap property. Always ask yourself: “Am I bubbling up/down correctly based on my heap type?”
3. Forgetting to Call heapifyUp or heapifyDown: After inserting or extracting, the heap property will be violated. Forgetting to call the corresponding heapify method will leave you with a non-functional heap.
4. Handling Empty Heaps/Single Elements: Always add checks for this.isEmpty() or this.size() === 1 in peek() and extractMin/Max() to prevent array access errors (undefined values) or incorrect logic.
5. Type Mismatches for Generic Heaps: If you were to make your heap generic (e.g., Heap<T>), you’d need a way to compare elements of type T. This often involves passing a custom comparator function to the constructor. For our number-only example, this isn’t an issue, but keep it in mind for more complex types.

To debug, you can add console.log statements inside heapifyUp and heapifyDown to print the heap array at each step, along with currentIndex and smallerChildIndex. This visualizes the bubbling process and helps pinpoint where the heap property is being violated.

Real-World Use Cases: Where Heaps and Priority Queues Shine

Heaps and Priority Queues are fundamental in computer science and appear in many critical applications:

1. Task Scheduling (Operating Systems): Operating systems use priority queues to manage processes. High-priority tasks (e.g., user input, critical system functions) are executed before lower-priority tasks, ensuring responsiveness and stability.
2. Shortest Path Algorithms (Dijkstra’s & Prim’s):
   • Dijkstra’s Algorithm for finding the shortest path in a graph uses a priority queue to efficiently select the next vertex to visit, always picking the one with the smallest known distance from the source.
   • Prim’s Algorithm for finding a Minimum Spanning Tree (MST) also uses a priority queue to greedily select the next edge that connects a new vertex to the MST with the smallest weight.
3. Event Simulation: In discrete event simulations, events are stored in a priority queue, ordered by their timestamp. The simulator always processes the earliest event next.
4. Data Compression (Huffman Coding): Huffman coding, a widely used data compression algorithm, builds its compression tree using a priority queue to repeatedly combine the two nodes with the lowest frequencies.
5. Top K Elements: Finding the “Top K” largest or smallest elements in a stream of data (e.g., top 10 most frequent words, top 5 highest scores) can be efficiently done using a Min-Heap (to find largest K) or a Max-Heap (to find smallest K) of size K.
6. Load Balancing: In distributed systems, a load balancer might use a priority queue to assign tasks to servers, prioritizing servers with less load or specific capabilities.
7. Heap Sort: Heaps are the basis of the Heap Sort algorithm, an efficient, in-place comparison-based sorting algorithm with O(N log N) time complexity.

The ability of heaps to quickly retrieve and update the highest (or lowest) priority item makes them indispensable in scenarios where efficient prioritization is key.

Summary

Phew! You’ve just conquered Heaps and Priority Queues, two incredibly powerful data structures. Let’s recap the key takeaways:

• Heaps are specialized tree-based data structures (usually binary trees) that maintain the heap property and are complete binary trees.
• They are efficiently represented using a simple array, where parent/child indices can be calculated arithmetically.
• Min-Heaps ensure the smallest element is always at the root, while Max-Heaps ensure the largest is at the root.
• A Priority Queue is an Abstract Data Type (ADT) that allows elements to be inserted with a priority and extracted based on that priority.
• Heaps are the most efficient way to implement Priority Queues, offering O(log N) time complexity for insert and extractMin/Max operations, and O(1) for peek.
• The core operations involve heapifyUp (bubbling an element up after insertion) and heapifyDown (bubbling an element down after extraction) to maintain the heap property.
• Heaps and Priority Queues are crucial in real-world applications like operating system scheduling, graph algorithms (Dijkstra’s, Prim’s), event simulation, and finding top K elements.

You’ve not only grasped the theoretical underpinnings but also built a functional Min-Priority Queue in TypeScript. This is a significant step forward in your DSA journey!

Next, we’ll dive into another fundamental data structure that deals with interconnectedness: Graphs. Get ready to explore nodes, edges, and the fascinating algorithms that traverse and analyze complex networks!

References

• Node.js v24.13.0 LTS Documentation
• TypeScript Handbook - Classes
• MDN Web Docs - Data structures - Heap
• GeeksforGeeks - Priority Queue
• GeeksforGeeks - Binary Heap

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.