Heaps Technique in DSA

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.