Heaps & Priority Queues

Open in Colab

Code from this lesson

Interactive Python notebookRun and edit this lesson's code right in your browser. It takes a few seconds to start.

// Heaps and Priority Queues - Greg Hogg DSA Course Materials Lecture 9

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

// Function for heap sort using a min-heap
std::vector<int> heapsort(const std::vector<int>& arr) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int num : arr) {
        minHeap.push(num);
    }
    std::vector<int> sortedArray;
    while (!minHeap.empty()) {
        sortedArray.push_back(minHeap.top());
        minHeap.pop();
    }
    return sortedArray;
}

int main() {
    // Min Heap operations
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    std::vector<int> A = {-4, 3, 1, 0, 2, 5, 10, 8, 12, 9};
    for (int num : A) {
        minHeap.push(num);
    }
    std::cout << "Min Heap built from array A" << std::endl;

    // Heap Push
    minHeap.push(4);
    std::cout << "Heap after push (adding 4)" << std::endl;

    // Heap Pop
    int min = minHeap.top();
    minHeap.pop();
    std::cout << "Extracted min: " << min << std::endl;

    // Heap Sort
    std::vector<int> sortedArray = heapsort({1, 3, 5, 7, 9, 2, 4, 6, 8, 0});
    std::cout << "Heap sorted array: ";
    for (int num : sortedArray) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Heap Push Pop
    minHeap.push(99);
    int pushPopResult = minHeap.top();
    minHeap.pop();
    std::cout << "Push pop result: " << pushPopResult << std::endl;

    // Peek at Min
    std::cout << "Min element: " << minHeap.top() << std::endl;

    // Max Heap operations
    std::priority_queue<int> maxHeap;
    std::vector<int> B = {-4, 3, 1, 0, 2, 5, 10, 8, 12, 9};
    for (int num : B) {
        maxHeap.push(num);
    }
    std::cout << "Max Heap built from array B" << std::endl;

    // Extract the largest element
    int largest = maxHeap.top();
    maxHeap.pop();
    std::cout << "Extracted largest: " << largest << std::endl;

    // Insert into Max Heap
    maxHeap.push(7);
    std::cout << "Max Heap after inserting 7" << std::endl;

    // Build heap from scratch
    std::vector<int> C = {-5, 4, 2, 1, 7, 0, 3};
    std::priority_queue<int> heapFromScratch;
    for (int num : C) {
        heapFromScratch.push(num);
        std::cout << "Heap size: " << heapFromScratch.size() << std::endl;
    }

    return 0;
}

// Heaps and Priority Queues - Greg Hogg DSA Course Materials Lecture 9

import java.util.PriorityQueue;

// Min Heap
public class Main {
    public static void main(String[] args) {
        // Build Min Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int[] A = {-4, 3, 1, 0, 2, 5, 10, 8, 12, 9};
        for (int num : A) {
            minHeap.add(num);
        }
        System.out.println("Min Heap: " + minHeap);

        // Heap Push (Insert element)
        minHeap.add(4);
        System.out.println("Heap after push: " + minHeap);

        // Heap Pop (Extract min)
        int min = minHeap.poll();
        System.out.println("Extracted min: " + min);
        System.out.println("Heap after pop: " + minHeap);

        // Heap Sort
        int[] sortedArray = heapsort(new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 0});
        System.out.println("Heap sorted array: " + java.util.Arrays.toString(sortedArray));

        // Heap Push Pop
        minHeap.add(99);
        int pushPopResult = minHeap.poll();
        System.out.println("Push pop result: " + pushPopResult);
        System.out.println("Heap after push-pop: " + minHeap);

        // Peek at Min
        System.out.println("Min element: " + minHeap.peek());
    }

    // Heap Sort using a min heap
    public static int[] heapsort(int[] arr) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : arr) {
            heap.add(num);
        }
        int[] sortedArray = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sortedArray[i] = heap.poll();
        }
        return sortedArray;
    }
}

// Max Heap
import java.util.PriorityQueue;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        // Build Max Heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int[] B = {-4, 3, 1, 0, 2, 5, 10, 8, 12, 9};
        for (int num : B) {
            maxHeap.add(num);
        }
        System.out.println("Max Heap: " + maxHeap);

        // Extract the largest element
        int largest = maxHeap.poll();
        System.out.println("Extracted largest: " + largest);

        // Insert into Max Heap
        maxHeap.add(7);
        System.out.println("Max Heap after inserting 7: " + maxHeap);

        // Build heap from scratch
        int[] C = {-5, 4, 2, 1, 7, 0, 3};
        PriorityQueue<Integer> heapFromScratch = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : C) {
            heapFromScratch.add(num);
            System.out.println("Heap: " + heapFromScratch + ", size: " + heapFromScratch.size());
        }

        // Handling tuples (here, using a custom comparator or additional structure)
    }
}

Uses a Node.js package, so it can't run in the browser.

// Heaps and Priority Queues - Greg Hogg DSA Course Materials Lecture 9

const { MinPriorityQueue, MaxPriorityQueue } = require('@datastructures-js/priority-queue');

// Min Heap
function minHeapOperations() {
    const minHeap = new MinPriorityQueue();
    const A = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9];
    A.forEach(num => minHeap.enqueue(num));
    console.log("Min Heap: ", minHeap.toArray());

// Heap Push (Insert element)
    minHeap.enqueue(4);
    console.log("Heap after push: ", minHeap.toArray());

// Heap Pop (Extract min)
    const min = minHeap.dequeue().element;
    console.log("Extracted min: ", min);
    console.log("Heap after pop: ", minHeap.toArray());

// Heap Sort
    const sortedArray = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
    console.log("Heap sorted array: ", sortedArray);

// Heap Push Pop
    minHeap.enqueue(99);
    const pushPopResult = minHeap.dequeue().element;
    console.log("Push pop result: ", pushPopResult);
    console.log("Heap after push-pop: ", minHeap.toArray());

// Peek at Min
    console.log("Min element: ", minHeap.front().element);
}

// Heap Sort using a min heap
function heapsort(arr) {
    const heap = new MinPriorityQueue();
    arr.forEach(num => heap.enqueue(num));
    const sortedArray = [];
    while (heap.size()) {
        sortedArray.push(heap.dequeue().element);
    }
    return sortedArray;
}

// Max Heap
function maxHeapOperations() {
    const maxHeap = new MaxPriorityQueue();
    const B = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9];
    B.forEach(num => maxHeap.enqueue(num));
    console.log("Max Heap: ", maxHeap.toArray());

// Extract the largest element
    const largest = maxHeap.dequeue().element;
    console.log("Extracted largest: ", largest);

// Insert into Max Heap
    maxHeap.enqueue(7);
    console.log("Max Heap after inserting 7: ", maxHeap.toArray());

// Build heap from scratch
    const C = [-5, 4, 2, 1, 7, 0, 3];
    const heapFromScratch = new MaxPriorityQueue();
    C.forEach(num => heapFromScratch.enqueue(num));
    console.log("Heap: ", heapFromScratch.toArray(), ", size: ", heapFromScratch.size());
}

// Run the functions
minHeapOperations();
maxHeapOperations();

Summary

Heaps are binary trees that maintain a specific order property: min-heaps have the smallest element at the root, while max-heaps have the largest. They support O(log n) insertion and extraction, and are ideal for priority queues, real-time scheduling, and heap sort.

Heaps & Priority Queues

A heap is a specialized binary tree used to quickly find and extract the minimum or maximum element. In a min-heap, the parent is less than or equal to its children; in a max-heap, the parent is greater than or equal to its children. Heaps are typically implemented as arrays for efficiency.

Priority Queues

Heaps are used to build priority queues, where elements are processed based on priority rather than order of arrival. Operations include push to insert and pop to extract the highest/lowest priority element—both in O(log n) time.

Applications

Heap Sort: Efficient sorting with O(n log n) complexity
Dijkstra’s Algorithm: Finding shortest paths in weighted graphs
Task Scheduling: Real-time systems and process prioritization

Common Operations

Insert: O(log n)
Extract Min/Max: O(log n)
Peek: O(1)

Conclusion

Heaps provide an optimal solution for problems requiring frequent retrieval of extremum values. Understanding how they are structured and manipulated is crucial for building efficient, real-time systems and solving graph-based problems.

Heaps and Priority Queues: Concepts and Operations

Heaps and priority queues refer to the same underlying data structure: a specialized binary tree used to manage prioritized data. They are highly efficient for retrieving the minimum or maximum element and are commonly implemented using arrays.

What Is a Heap?

A heap is a complete binary tree that satisfies the heap property:

Min Heap: The value of each node is less than or equal to the values of its children. The smallest value is at the root.
Max Heap: The value of each node is greater than or equal to its children. The largest value is at the root.

Heaps are particularly useful for implementing priority queues, where each element has a priority, and the highest (or lowest) priority element is always accessed first.

Array Representation of Heaps

Heaps are efficiently represented as arrays. In a 0-based array:

The parent of the node at index i is at Math.floor((i - 1) / 2)
The left child is at 2 * i + 1
The right child is at 2 * i + 2

This representation allows heap operations to be implemented efficiently without the need for explicit node references.

Key Heap Operations

1. Heapify (Building a Heap)

Heapify is the process of converting an unordered array into a valid heap. It starts from the last non-leaf node and performs a sift down operation for each node up to the root. This ensures the heap property is maintained across all subtrees.

Time Complexity: O(n)
Space Complexity: O(1) (in-place)
Note: Building a heap by inserting one element at a time using `Heap push` takes O(n log n) time, which is less efficient.

2. Heap Pop (Extract Min/Max)

Heap pop removes and returns the root element (minimum or maximum). After removal, the last element is moved to the root, and a sift down operation restores the heap property.

Time Complexity: O(log n)
Reason: The height of a binary heap is log n, and the operation moves down one path.

3. Heap Push (Insert)

Heap push inserts a new element at the end of the heap (array) and performs a sift up to maintain heap order. The element is compared with its parent and swapped upward if needed.

Time Complexity: O(log n)
Reason: At most, the element moves up the height of the tree.

4. Heap Peak (Peek)

Heap peak returns the root element without removing it. For Min Heaps, this is the smallest element; for Max Heaps, the largest.

Time Complexity: O(1)
Reason: The root is always at index 0 in the array.

5. Heap Push Pop

Heap push pop performs a push followed by a pop in a single step, which is more efficient than calling them separately. It maintains the heap structure throughout.

Time Complexity: O(log n)

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses the heap data structure. It works by:

Building a Max Heap from the unsorted array.
Repeatedly removing the maximum element (root) and placing it at the end of the array.

Time Complexity: O(n log n)
Space Complexity: O(1) if done in-place; O(n) if a separate array is used.

Practical Usage: Python's `heapq` Library

Python’s built-in heapq library implements a Min Heap and provides efficient functions for common heap operations:

heapq.heapify() – Converts a list into a heap in-place.
heapq.heappush(heap, item) – Adds an item while maintaining heap order.
heapq.heappop(heap) – Removes and returns the smallest item.
heapq.heappushpop(heap, item) – Pushes a new item and pops the smallest one in one step.

Using Tuples as Priorities

In heapq, heaps can contain tuples like (priority, value). The heap compares elements by the first tuple item, making it ideal for implementing priority queues. If priorities are equal, it compares the next tuple element.

Simulating a Max Heap in Python

Since heapq is a Min Heap by default, you can simulate a Max Heap by inserting the negated value. When retrieving values, simply negate again:

Insert with heappush(heap, -value)
Pop with -heappop(heap)

Additional Considerations

Length of heap: Using len(heap) is O(1).
Peek at minimum: Accessing heap[0] is also O(1).

NEW!Need help landing software roles? 💡

AlgoMap.io

Heaps & Priority Queues

Code from this lesson

Summary

Heaps & Priority Queues

Priority Queues

Applications

Common Operations

Conclusion

Heaps and Priority Queues: Concepts and Operations

What Is a Heap?

Array Representation of Heaps

Key Heap Operations

1. Heapify (Building a Heap)

2. Heap Pop (Extract Min/Max)

3. Heap Push (Insert)

4. Heap Peak (Peek)

5. Heap Push Pop

Heap Sort

Practical Usage: Python's heapq Library

Using Tuples as Priorities

Simulating a Max Heap in Python

Additional Considerations

Practical Usage: Python's `heapq` Library