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

Operation	Time Complexity
Insertion	$O(\log n)$
Deletion	$O(\log n)$
Build Heap	$O(n)$
Heap Sort	$O(n \log n)$