Skip to content

Latest commit

 

History

History
442 lines (315 loc) · 9.04 KB

02.BinaryMaxHeap.md

File metadata and controls

442 lines (315 loc) · 9.04 KB

🍕 Binary Max Heap

🧾 Problem / Goal

Implement a binary max-heap using an array, supporting operations:

  • Insert an element
  • Get maximum element
  • Extract (remove + return) maximum
  • Increase the key at some index
  • Delete an element at a given index

This is very similar to the binary min-heap — only the comparisons flip sign.

A max-heap satisfies:

For every node i: arr[i] >= arr[left(i)] and arr[i] >= arr[right(i)] (if those children exist).

🧠 Intuition: Max-Heap as an Array

We store the heap in a simple array and use index math to simulate a complete binary tree:

  • parent(i) = (i - 1) / 2
  • left(i) = 2*i + 1
  • right(i) = 2*i + 2

The root element is at arr[0] and is always the maximum.

Visually, the heap is always a complete binary tree (all levels filled except maybe the last, and that only from left to right).

🧱 Class Structure Overview

class BinaryHeap {
public:
    int capacity; // max possible size
    int size;     // current number of elements
    int *arr;     // array to store heap elements

    BinaryHeap(int cap);
    int parent(int i);
    int left(int i);
    int right(int i);
    void swap(int* x, int* y);

    void Insert(int x);
    void Heapify(int ind);
    int getMax();
    int ExtractMax();
    void IncreaseKey(int i, int val);
    void Delete(int i);
    void print();
};

Pretty classic structure for a heap.

⚙️ Operation-by-Operation Breakdown

🔹 1. Insert into Max-Heap

Goal

Insert a new key and maintain the max-heap property.

Logic

  1. Place the new key at the end: arr[size].

  2. “Bubble it up” while it’s greater than its parent:

    • Swap with parent.
    • Move index up to parent.

  3. Stop when:

    • It becomes the root (index == 0), or
    • Its parent is larger or equal.

Code

void Insert(int x) {
    if (size == capacity) {
        cout << "Heap Overflow" << endl;
        return;
    }

    arr[size] = x;
    int k = size;
    size++;

    // Bubble up while parent is smaller (max-heap)
    while (k != 0 && arr[parent(k)] < arr[k]) {
        swap(&arr[parent(k)], &arr[k]);
        k = parent(k);
    }
}

Time Complexity: O(log n) (height of the heap).

🔹 2. Heapify (Downward Heap Fix)

Goal

Given a node index ind, assume its subtrees are heaps, but arr[ind] might be smaller than one of its children. Fix this violation by “pushing it down”.

Logic

  1. Compute left and right child indices.

  2. Find largest among ind, left, right.

  3. If a child is larger than the current node:

    • Swap node with the larger child.
    • Recursively Heapify() on that child index.

Code

void Heapify(int ind) {
    int li = left(ind);
    int ri = right(ind);
    int largest = ind;

    if (li < size && arr[li] > arr[largest])
        largest = li;
    if (ri < size && arr[ri] > arr[largest])
        largest = ri;

    if (largest != ind) {
        swap(&arr[ind], &arr[largest]);
        Heapify(largest);
    }
}

Time Complexity: O(log n)

Used in ExtractMax and in heap-building logic (if you add that later).

🔹 3. Get Maximum

Goal

Return the largest element in the heap.

That’s always at arr[0] in a max-heap.

int getMax() {
    if (size == 0) {
        cout << "Heap is empty" << endl;
        return INT_MIN;
    }
    return arr[0];
}

Time Complexity: O(1).

🔹 4. ExtractMax

Goal

Remove and return the maximum element (the root).

Logic

  1. Save arr[0] as maxi.
  2. Move last element (arr[size-1]) to root.
  3. Decrease size.
  4. Call Heapify(0) to fix the heap property.

Code

int ExtractMax() {
    if (size <= 0)
        return INT_MIN;

    if (size == 1) {
        size--;
        return arr[0];
    }

    int maxi = arr[0];
    arr[0] = arr[size - 1];
    size--;
    Heapify(0);

    return maxi;
}

Time Complexity: O(log n)

🔹 5. IncreaseKey

In a max-heap, a common operation is to increase the value at index i, and then float it upwards if needed.

Logic

  1. Set arr[i] = val (assuming val ≥ old value).

  2. While it is greater than its parent:

    • Swap with parent.
    • Move i to parent index.

Code

void IncreaseKey(int i, int val) {
    arr[i] = val;

    // Bubble up while parent is smaller
    while (i != 0 && arr[parent(i)] < arr[i]) {
        swap(&arr[parent(i)], &arr[i]);
        i = parent(i);
    }
}

Time Complexity: O(log n)

Note: In a bulletproof version, you’d check i is in range, and maybe ensure val >= oldValue.

🔹 6. Delete

Classic heap trick:

  1. Increase the value at index i to +∞ (here INT_MAX) so it becomes the maximum.
  2. It will bubble up to the root via IncreaseKey.
  3. Call ExtractMax() to remove it.

Code

void Delete(int i) {
    // Set to very large, move to root, then extract
    IncreaseKey(i, INT_MAX);
    ExtractMax();
}

Time Complexity: O(log n) for IncreaseKey + O(log n) for ExtractMax → still O(log n).

🔹 7. Utility: print

void print() {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Good for debugging. The heap contents are not sorted, they’re in heap order.

✅ Full Code (as given, structurally sound)

Just re-listing with slight spacing/styling:

#include <bits/stdc++.h>
using namespace std;

class BinaryHeap {
public:
    int capacity;
    int size;
    int *arr;

    BinaryHeap(int cap) {
        capacity = cap;
        size = 0;
        arr = new int[capacity];
    }

    int parent(int i) { return (i - 1) / 2; }
    int left(int i)   { return 2 * i + 1; }
    int right(int i)  { return 2 * i + 2; }

    void swap(int* x, int* y) {
        int temp = *x;
        *x = *y;
        *y = temp;
    }

    // Insert into max-heap
    void Insert(int x) {
        if (size == capacity) {
            cout << "Heap Overflow" << endl;
            return;
        }

        arr[size] = x;
        int k = size;
        size++;

        // Bubble up while parent is smaller (for max-heap)
        while (k != 0 && arr[parent(k)] < arr[k]) {
            swap(&arr[parent(k)], &arr[k]);
            k = parent(k);
        }
    }

    // Heapify for max-heap (push down)
    void Heapify(int ind) {
        int li = left(ind);
        int ri = right(ind);
        int largest = ind;

        if (li < size && arr[li] > arr[largest])
            largest = li;
        if (ri < size && arr[ri] > arr[largest])
            largest = ri;

        if (largest != ind) {
            swap(&arr[ind], &arr[largest]);
            Heapify(largest);
        }
    }

    int getMax() {
        if (size == 0) {
            cout << "Heap is empty" << endl;
            return INT_MIN;
        }
        return arr[0];
    }

    int ExtractMax() {
        if (size <= 0)
            return INT_MIN;

        if (size == 1) {
            size--;
            return arr[0];
        }

        int maxi = arr[0];
        arr[0] = arr[size - 1];
        size--;
        Heapify(0);

        return maxi;
    }

    // For max-heap we usually INCREASE key to bubble it up.
    void IncreaseKey(int i, int val) {
        arr[i] = val;

        // Bubble up while parent is smaller
        while (i != 0 && arr[parent(i)] < arr[i]) {
            swap(&arr[parent(i)], &arr[i]);
            i = parent(i);
        }
    }

    void Delete(int i) {
        // Set to very large, move to root, then extract
        IncreaseKey(i, INT_MAX);
        ExtractMax();
    }

    void print() {
        for (int i = 0; i < size; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    BinaryHeap h(20);
    h.Insert(4);
    h.Insert(1);
    h.Insert(2);
    h.Insert(6);
    h.Insert(7);
    h.Insert(3);
    h.Insert(8);
    h.Insert(5);

    cout << "Max value is: " << h.getMax() << endl;

    h.Insert(10);
    cout << "Max value is: " << h.getMax() << endl;

    h.IncreaseKey(3, 20); // increase value at index 3
    cout << "Max value is: " << h.getMax() << endl;

    h.ExtractMax();
    cout << "Max value is: " << h.getMax() << endl;

    h.Delete(0);
    cout << "Max value is: " << h.getMax() << endl;

    return 0;
}

If you want to make it more robust/production-ready, you could add:

  • A destructor (~BinaryHeap) to delete[] arr.
  • Bounds checks in IncreaseKey, Delete.
  • Replace raw pointer with vector<int>.

⏱ Complexity Summary

For a heap with n elements:

Operation Time
Insert O(log n)
Heapify O(log n)
ExtractMax O(log n)
IncreaseKey O(log n)
Delete O(log n)
getMax O(1)

Space: O(capacity).

💡 Interview / Learning Notes

  • You now have both min-heap and max-heap implemented manually — that’s big for understanding priority_queue.
  • In C++, priority_queue<int> is a max-heap by default; your class is essentially a manual version of that.
  • You can easily template this class to support any comparable type, not just int.