Heap Data Structure | Insertion and Deletion in Max Heap

1. Introduction and Real-World Use Cases

A Heap is a specialized tree-based data structure that satisfies the heap property and is fundamental in computer science for priority-based processing.

Real-Life Analogy

Imagine an emergency room at a hospital. Patients do not necessarily get treated in the order they arrive (First-In, First-Out, like a Queue). Instead, patients with life-threatening conditions (highest priority) are treated first, followed by less critical patients. Similarly, in operating systems, critical background processes or high-priority threads must be scheduled and executed before routine tasks.

Key Technical Applications

• Computer Networks: Routing packets where high-priority traffic is sent ahead of standard data.
• Operating Systems: Process schedulers prioritizing critical system tasks over user-level background operations.
• Graph Algorithms: Efficient implementation of Dijkstra's Shortest Path and Prim's Minimum Spanning Tree algorithms using Priority Queues.

2. Complete Binary Tree (CBT) Definition & Mental Model

Before defining a Heap, we must understand its structural foundation: the Complete Binary Tree (CBT). A CBT is distinct from a Binary Search Tree (BST).

Formal Rules of a Complete Binary Tree

1. All levels must be completely filled, except possibly the very last level.
2. At the last level, nodes must be filled from left to right. Gaps (missing nodes on the left with populated nodes on the right) are strictly forbidden.

CBT vs. Non-CBT Structural Validation

3. Types of Heaps: Max Heap vs. Min Heap

A Heap is always implemented as a Complete Binary Tree and is categorized into two types based on how data is ordered relative to parent and child nodes.

Note: Duplicate values are allowed in heaps, which is why the inequality uses greater-than-or-equal-to ($\ge$) or less-than-or-equal-to ($\le$).

4. Naive vs. Better Approach: Array-Based Heap Representation

While trees can be implemented using linked list nodes with pointers (left and right), maintaining a Complete Binary Tree and performing upward/downward traversals via pointers is inefficient ($O(N)$ overhead just to find the insertion spot and complex parent-pointer lookups).

The Better Approach: Contiguous Array Representation

Because a Heap is a Complete Binary Tree, it can be stored compactly in a standard array without wasting space on null pointers. By mapping levels sequentially from top-to-bottom and left-to-right, we establish a clean mathematical index mapping between parents and children.

Tree Representation:                  Array Representation Indexing:
          (40) [Index 0]               Index:  0   1   2   3   4   5   6
         /    \                        Value: 40  32  18  13  31  12  19
      (32)    (18) [Indices 1, 2]
      /   \      \
    (13)  (31)   (12) [Indices 3, 4, 5]

Mathematical Index Mapping Formulas

Given any node at index i (0-based indexing):

• Left Child Index: 2 * i + 1
• Right Child Index: 2 * i + 2
• Parent Index: (i - 1) / 2 (using integer division)

5. Step-by-Step Evolution: Insertion in Max Heap

When inserting a new element into a Max Heap, we must maintain two invariants:

1. Structural Invariant: The tree must remain a Complete Binary Tree (insert at the next available spot on the last level, i.e., the end of the array).
2. Order Invariant: The Max Heap property must hold (parent must be greater than or equal to its children). If violated, we perform "Step Up" (Upheap / Percolate Up) operations.

Insertion Flow Walkthrough

1. Append the new element at the next available slot (the end of the array / bottom-right of the CBT).
2. Compare the inserted node with its parent: Parent Index = (i - 1) / 2.
3. If Parent < Current Node, swap them.
4. Repeat the comparison and swap upward until the parent is greater, or the node reaches the root index (0).

6. Complete Practical Code Implementation (C++)

Below is the production-ready C++ implementation of a Max Heap demonstrating class design, array allocation, boundary checks (overflow handling), insertion (Step Up), and printing.

#include <iostream>
using namespace std;

class MaxHeap {
private:
    int* arr;
    int size;       // Current number of elements in the heap
    int totalSize;  // Maximum capacity of the underlying array

public:
    // Constructor to initialize the heap capacity
    MaxHeap(int n) {
        totalSize = n;
        arr = new int[totalSize];
        size = 0;
    }

    // Destructor to free dynamically allocated memory
    ~MaxHeap() {
        delete[] arr;
    }

    // Insert operation into the Max Heap
    void insert(int val) {
        // 1. Check for Overflow
        if (size == totalSize) {
            cout << "Heap Overflow! Cannot insert " << val << endl;
            return;
        }

        // 2. Insert element at the end of the array (CBT structure maintained)
        int index = size;
        arr[index] = val;
        size++;

        // 3. Step Up (Percolate Up) to maintain Max Heap property
        while (index > 0) {
            int parentIndex = (index - 1) / 2;

            if (arr[parentIndex] < arr[index]) {
                // Swap parent and child
                int temp = arr[parentIndex];
                arr[parentIndex] = arr[index];
                arr[index] = temp;

                // Move up to parent's index
                index = parentIndex;
            } else {
                // Heap property satisfied
                break;
            }
        }
        cout << val << " inserted into the heap successfully.\n";
    }

    // Print current heap elements
    void printHeap() {
        if (size == 0) {
            cout << "Heap is empty!\n";
            return;
        }
        cout << "Heap elements (Array representation): ";
        for (int i = 0; i < size; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    // Create a Max Heap with a total capacity of 6 elements
    MaxHeap h1(6);

    h1.insert(4);
    h1.insert(14);
    h1.insert(11);
    h1.insert(24);
    h1.insert(10);
    h1.insert(5);

    // Attempting 7th insertion to trigger Heap Overflow
    h1.insert(50);

    h1.printHeap();
    return 0;
}

7. Deletion in Max Heap & The "Heapify" (Step Down) Process

In a standard Heap/Priority Queue, deletion is always performed on the root node (the maximum element in a Max Heap). Deleting arbitrary middle nodes breaks the CBT structure; hence, we use a specific replacement strategy.

Step-by-Step Deletion Workflow

1. Check for Underflow: If size == 0, the heap is empty.
2. Extract Root: Save or report the root element (arr[0]) as the deleted value.
3. Replace Root: Move the last element of the heap (arr[size - 1]) to the root position (arr[0]).
4. Shrink Heap: Decrement size by 1.
5. Step Down (Heapify / Percolate Down): Restore the Max Heap property by comparing the new root with its children, swapping it with the largest child, and repeating downward until order is restored.

Heapify Algorithm Logic

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

    // Check if left child exists and is greater than current root
    if (leftChild < size && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }

    // Check if right child exists and is greater than current largest
    if (rightChild < size && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // If the largest is not the parent, swap and recursively heapify downwards
    if (largest != index) {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;

        heapify(largest); // Recursive step down
    }
}

8. Summary and Key Takeaways

• Complete Binary Tree Foundation: Heaps must be complete binary trees where all levels are fully filled except possibly the last, which is filled strictly from left to right.
• Max Heap Invariant: Every parent node must be greater than or equal to its child nodes, placing the absolute maximum element at the root (Index 0).
• Array Storage Efficiency: Using contiguous arrays avoids pointer overhead, enabling quick index navigation via 2*i + 1 (left child), 2*i + 2 (right child), and (i - 1) / 2 (parent).
• Insertion ("Step Up"): Elements are added at the end of the array and percolated upward by comparing against parents, taking $O(\log N)$ time in the worst case.
• Deletion ("Step Down" / Heapify): Root deletion replaces the top element with the last CBT element, followed by percolating downward by swapping with the largest child, taking $O(\log N)$ time.
• Heap Overflow & Underflow: Array implementations require strict bounds checking before inserting (overflow) or deleting (underflow).
• Upcoming Optimizations: While inserting $N$ elements one-by-one takes $O(N \log N)$ time, an advanced linear-time $O(N)$ heap construction method exists for bulk data initialization.