Heaps

Heaps

A heap is a special tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues and is highly efficient for operations like finding the minimum or maximum element.

Heap Properties

1. Complete Binary Tree:

   • A heap is always a complete binary tree, meaning all levels are completely filled except possibly the last level, which is filled from left to right.

2. Heap Order Property:

   • Max-Heap: The value of the parent node is greater than or equal to the values of its children.
   • Min-Heap: The value of the parent node is less than or equal to the values of its children.

Types of Heaps

1. Max-Heap:

   • The root node contains the largest element.
   • Example:

            50
          /    \
        30      40
       /  \    /  \
     10   20  15  25
     

2. Min-Heap:

   • The root node contains the smallest element.
   • Example:

            10
          /    \
        20      15
       /  \    /  \
     50   30  25  40
     

Heap Operations

Heaps support the following main operations:

1. Insertion

To insert an element into a heap:

1. Add the element at the next available position (at the bottom level).
2. "Heapify Up" to maintain the heap property:
   • Compare the inserted node with its parent.
   • Swap them if they violate the heap property.
   • Repeat until the heap property is restored.

C++ Implementation:

#include <iostream>
#include <vector>
using namespace std;

class MaxHeap {
    vector<int> heap;

    void heapifyUp(int index) {
        while (index > 0 && heap[index] > heap[(index - 1) / 2]) {
            swap(heap[index], heap[(index - 1) / 2]); // Swap with parent
            index = (index - 1) / 2; // Move to the parent's index
        }
    }

public:
    void insert(int value) {
        heap.push_back(value); // Add at the end
        heapifyUp(heap.size() - 1); // Restore heap property
    }

    void display() {
        for (int val : heap) cout << val << " ";
        cout << endl;
    }
};

int main() {
    MaxHeap h;
    h.insert(50);
    h.insert(30);
    h.insert(40);
    h.insert(10);
    h.insert(20);
    h.insert(15);

    h.display(); // Output: 50 30 40 10 20 15
    return 0;
}

2. Deletion (Removing the Root)

To delete the root element:

1. Replace the root with the last element.
2. Remove the last element.
3. "Heapify Down" to maintain the heap property:
   • Compare the root with its largest (or smallest) child.
   • Swap them if they violate the heap property.
   • Repeat until the heap property is restored.

C++ Implementation:

class MaxHeap {
    vector<int> heap;

    void heapifyDown(int index) {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heap.size() && heap[leftChild] > heap[largest])
            largest = leftChild;
        if (rightChild < heap.size() && heap[rightChild] > heap[largest])
            largest = rightChild;

        if (largest != index) {
            swap(heap[index], heap[largest]);
            heapifyDown(largest); // Recursively heapify the affected subtree
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    void deleteRoot() {
        if (heap.empty()) return;
        heap[0] = heap.back(); // Replace root with last element
        heap.pop_back(); // Remove last element
        heapifyDown(0); // Restore heap property
    }

    void display() {
        for (int val : heap) cout << val << " ";
        cout << endl;
    }
};

Heapify

Heapify is the process of rearranging elements to maintain the heap property. It is often used when building a heap from an array.

Building a Heap

1. Start from the last non-leaf node.
2. Call heapifyDown for each node, moving upwards.

Time Complexity:

• Building a heap from $n$ elements: $O(n)$.

Applications of Heaps

1. Priority Queues:
   • Heaps are used to implement efficient priority queues.
   • Insertion and deletion are $O(\log n)$, and accessing the maximum or minimum is $O(1)$.
2. Heap Sort:
   • A sorting algorithm that uses a heap to sort elements.
   • Time Complexity: $O(n \log n)$.
3. Shortest Path Algorithms:
   • Used in algorithms like Dijkstra's for efficiently managing priority queues.
4. Scheduling Problems:
   • Task scheduling and load balancing.
5. Median Finding:
   • Heaps are used to find the median in a stream of numbers.

Heap Sort

Heap sort uses a max-heap to sort an array in ascending order:

1. Build a max-heap from the array.
2. Repeatedly remove the root (largest element) and place it at the end of the array.
3. Restore the heap property for the remaining elements.

C++ Implementation:

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // Build a max-heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements from the heap
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]); // Move current root to end
        heapify(arr, i, 0); // Restore heap property
    }
}

int main() {
    vector<int> arr = {50, 30, 40, 10, 20, 15};
    heapSort(arr);

    for (int val : arr) cout << val << " ";
    // Output: 10 15 20 30 40 50
    return 0;
}

Time Complexities of Heap Operations