Heaps Technique in DSA

Heaps Technique in DSA | Max Heap, Min Heap, and Applications

Heaps in a Nutshell

A complete binary tree where each parent satisfies a specific property compared to its children.
Supports efficient insertion, deletion, and extraction of minimum or maximum element.
Commonly used in priority queues and algorithms like Dijkstra and Heapsort.

What is the Heap Technique?

The Heap Technique is a method of organizing elements in a binary tree structure where the parent node always maintains a relationship with its children based on either:

Max Heap: Parent ≥ Children
Min Heap: Parent ≤ Children

Heaps are typically implemented as arrays and are ideal for scenarios requiring repeated access to the largest or smallest element.

Types of Heaps

Max Heap: The root is the maximum. Every parent is greater than or equal to its children.
Min Heap: The root is the minimum. Every parent is less than or equal to its children.

Common Heap Operations

Insert: Add a new element while maintaining the heap property.
Delete: Remove the top element (max or min), then re-heapify.
Heapify: Convert an array into a valid heap.

Pseudocode: Inserting into a Heap

// Insert value into heap and bubble it up
function insert(heap, value):
    heap.append(value)
    index = heap.length - 1

    while index > 0:
        parent = floor((index - 1) / 2)
        if heap[parent] < heap[index]:  // Max Heap
            swap(heap[parent], heap[index])
            index = parent
        else:
            break

Pseudocode: Heapify an Array

// Heapify subtree rooted at index 'i' for Max Heap
function heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr[i], arr[largest])
        heapify(arr, n, largest)

Pseudocode: Build Max Heap from Unordered Array

function buildMaxHeap(arr):
    n = arr.length
    for i from floor(n/2) - 1 down to 0:
        heapify(arr, n, i)

Applications of Heap Technique

Priority Queue: Heaps allow you to always access the highest or lowest priority item in O(1) and insert/delete in O(log n).
Heapsort: A sorting algorithm using the heap property to sort in O(n log n) time.
Top-K Elements: Min heap (for top K largest) or Max heap (for top K smallest).
Dijkstra’s Shortest Path: Uses a min heap (priority queue) to efficiently fetch the closest node.
Median in a Stream: Maintain a max heap and min heap to find running median in O(log n).

Example: Find K Largest Elements

Problem: Given an array, return the K largest elements in sorted order.

Solution: Use a Min Heap of size K. Iterate through the array, and:

If heap size < K, insert element.
If element > min of heap, replace min and re-heapify.

Pseudocode

function kLargestElements(arr, K):
    minHeap = new MinHeap()

    for num in arr:
        if minHeap.size() < K:
            minHeap.insert(num)
        else if num > minHeap.peek():
            minHeap.pop()
            minHeap.insert(num)

    return minHeap.toSortedArray()

Time and Space Complexity

Insert/Delete: O(log n)
Access Top: O(1)
Build Heap: O(n)

When to Use Heap Technique

You need to repeatedly access the max/min element.
Maintaining a dynamic dataset with changing priorities.
Solving problems involving scheduling, ranking, or optimization.

Advantages and Disadvantages

Advantages

Efficient priority access with log-time updates.
Simple array-based implementation.
Supports partial sorting (top-k elements).

Disadvantages

Does not support fast arbitrary search (like a HashMap).
Limited to scenarios where order is based on priority comparisons only.

Conclusion

The Heap Technique is vital in DSA for building efficient solutions to problems that require order-based access. Whether you're sorting, managing priorities, or scheduling, heaps offer a structured and performant approach to maintaining maximum or minimum values dynamically.