Heap Algorithms

Heap Algorithms Overview

Heap-based algorithms utilize the properties of a heap data structure, which is a complete binary tree that satisfies either the max-heap or min-heap property.

• Max-Heap: In a max-heap, the value of each node is greater than or equal to the values of its children, and the largest element is always at the root.
• Min-Heap: In a min-heap, the value of each node is smaller than or equal to the values of its children, and the smallest element is always at the root.

Heap-based algorithms are particularly useful for solving problems where repeated access to the largest or smallest elements is needed. The most common heap algorithms are used for sorting (Heap Sort), priority queues, and finding the k-th largest/smallest element.

Common Heap Algorithms

1. Heapify

The heapify algorithm is a crucial operation used to maintain the heap property. It ensures that a subtree rooted at a given node satisfies the heap property. It is used to build a heap and to restore the heap property after extraction.

• Time Complexity: O(log n) (since it traverses from a node to a leaf)
• Space Complexity: O(1) (in-place operation)

Heapify Pseudocode:

// Helper function to maintain the heap property
void heapify(int arr[], int n, int i) {
    int largest = i;         // Initialize largest as root
    int left = 2 * i + 1;    // Left child
    int right = 2 * i + 2;   // Right child

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // If largest is not root, swap and recursively heapify the affected subtree
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // Recursively heapify the affected subtree
    }
}

2. Building a Heap (Heap Construction)

Heap construction is the process of converting an unordered array into a heap. This can be done in O(n) time by calling heapify() on each non-leaf node, starting from the last non-leaf node down to the root.

• Time Complexity: O(n) (more efficient than repeatedly applying heapify in O(log n) for each element)
• Space Complexity: O(1)

Heap Construction Pseudocode:

void buildHeap(int arr[], int n) {
    // Start from the last non-leaf node and apply heapify
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

3. Extracting the Root (Max or Min)

In a heap, the root (first element in the array) is always the maximum element in a max-heap or the minimum element in a min-heap. Extracting the root involves swapping it with the last element and then calling heapify on the new root to restore the heap property.

• Time Complexity: O(log n) (heapify takes O(log n) time)
• Space Complexity: O(1)

Extract Root Pseudocode:

int extractMax(int arr[], int &n) {
    if (n <= 0) return -1;  // Heap is empty
    
    // The root of the heap (arr[0]) is the largest
    int root = arr[0];

    // Move the last element to the root
    arr[0] = arr[n - 1];
    n--;  // Decrease the size of the heap
    
    // Restore the heap property
    heapify(arr, n, 0);

    return root;
}

4. Heap Sort

Heap Sort is an efficient comparison-based sorting algorithm that utilizes a max-heap (or min-heap for reverse order). It works by building a heap from the input array and repeatedly extracting the root element, which is placed in the correct position in the array.

• Time Complexity: O(n log n)
• Space Complexity: O(1) (in-place)

Heap Sort Pseudocode:

void heapSort(int arr[], int n) {
    // Step 1: Build a max-heap
    buildHeap(arr, n);

    // Step 2: Extract elements one by one from the heap
    for (int i = n - 1; i >= 1; i--) {
        // Move the current root to the end
        swap(arr[0], arr[i]);

        // Heapify the root of the reduced heap
        heapify(arr, i, 0);
    }
}

5. Priority Queue (Heap-based)

A priority queue is an abstract data structure that supports efficient insertion and extraction of the highest (or lowest) priority element. The priority queue can be implemented using a heap. A max-heap can implement a max-priority queue, and a min-heap can implement a min-priority queue.

Operations:

• Insert (push): Add an element to the heap and restore the heap property.
• Extract (pop): Remove and return the root element, then restore the heap property.

Time Complexity:

• Insert: O(log n)
• Extract: O(log n)

Priority Queue Implementation:

class PriorityQueue {
    vector<int> heap;
    
public:
    // Insert an element
    void insert(int value) {
        heap.push_back(value);  // Add the element to the end
        int index = heap.size() - 1;

        // Restore the heap property by bubbling up
        while (index > 0 && heap[parent(index)] < heap[index]) {
            swap(heap[index], heap[parent(index)]);
            index = parent(index);
        }
    }

    // Extract the root (max element)
    int extractMax() {
        if (heap.size() == 0) return -1;  // Empty heap
        
        // The root is the max element
        int root = heap[0];
        
        // Move the last element to the root
        heap[0] = heap.back();
        heap.pop_back();
        
        // Restore the heap property by bubbling down
        heapify(heap, heap.size(), 0);

        return root;
    }

    int parent(int index) {
        return (index - 1) / 2;
    }

    int leftChild(int index) {
        return 2 * index + 1;
    }

    int rightChild(int index) {
        return 2 * index + 2;
    }
};

6. Finding K-th Largest/Smallest Element

You can use a min-heap to find the k-th largest element or a max-heap to find the k-th smallest element in an array.

Approach:

1. Build a heap of size k by inserting the first k elements.
2. For each subsequent element in the array, compare it with the root of the heap:
   • If the element is larger (in a min-heap), replace the root with the new element and heapify.
   • Otherwise, discard the element.
3. After processing all elements, the root of the heap will be the k-th largest element.

Time Complexity: O(n log k)

• Building the heap: O(k)
• For each element: O(log k)

Finding k-th Largest (Min-Heap):

int kthLargest(int arr[], int n, int k) {
    // Step 1: Build a min-heap of size k
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int i = 0; i < k; i++) {
        minHeap.push(arr[i]);
    }

    // Step 2: Process the remaining elements
    for (int i = k; i < n; i++) {
        if (arr[i] > minHeap.top()) {
            minHeap.pop();
            minHeap.push(arr[i]);
        }
    }

    // The root of the heap is the k-th largest element
    return minHeap.top();
}

Heap Algorithm Applications

• Heap Sort: Efficient sorting algorithm with O(n log n) time complexity.
• Priority Queue: Efficiently manages a collection of elements where the highest or lowest priority element is always accessible.
• Scheduling Problems: Used in scheduling algorithms like Dijkstra's Algorithm (shortest path) and Huffman Coding (data compression).
• K-th Largest/Smallest Element: Efficiently finding the k-th largest or smallest element in an unsorted array.

Summary

Heap-based algorithms are powerful and efficient, especially for problems involving priority queues, sorting (Heap Sort), and finding the k-th largest/smallest elements. The fundamental operations on heaps are heapify, building the heap, extracting elements, and maintaining the heap property. These operations all run in O(log n) time, making heaps a great choice for dynamic data processing with