Binary Heap

 

📚 What is a Binary Heap?

A Binary Heap is a complete binary tree that satisfies the heap property.

• Complete Binary Tree: All levels are completely filled except possibly the last level, and the last level has all nodes as left as possible.

• Heap Property:

  • Max-Heap: The value of each parent node is greater than or equal to its child nodes.

  • Min-Heap: The value of each parent node is less than or equal to its child nodes.

---

🔥 Types of Binary Heaps

Max Heap
➔ Root node has the largest value.
➔ Each parent is ≥ its children.

Min Heap
➔ Root node has the smallest value.
➔ Each parent is ≤ its children.

---

📈 How is a Binary Heap Represented?

• Using an array (very important!)

• If a node is at index i, then:

  • Left Child is at index 2*i + 1

  • Right Child is at index 2*i + 2

  • Parent is at index (i - 1)/2

Array representation saves space and makes operations efficient.

---

⚡ Operations on Binary Heap

1. Insert a Node

• Add the new element at the end (next available spot).

• "Heapify Up" → Move up until the heap property is restored.

Algorithm for Insert in Max-Heap:

Insert(element)
    1. Add element at the end.
    2. Compare with parent; if larger, swap.
    3. Repeat step 2 until heap property is restored.

2. Delete Root Node (Extract Max or Min)

• Root holds max (in Max-Heap) or min (in Min-Heap).

• Remove the root node.

• Replace it with the last node.

• "Heapify Down" → Move down to maintain heap property.

Algorithm for Delete in Max-Heap:

DeleteRoot()
    1. Replace root with the last element.
    2. Remove the last element.
    3. Compare root with children; if smaller, swap with the larger child.
    4. Repeat step 3 until heap property is restored.

3. Heapify

• Heapify is the process of adjusting a node and its subtree to satisfy the heap property.

• Used in insertion, deletion, and heap creation.

There are two types:

• Heapify Up: when inserting

• Heapify Down: when deleting root

---

🛠️ Important Points

• Insertion → O(log n) time

• Deletion → O(log n) time

• Building a heap from array → O(n) time

• Get Maximum or Minimum  → O(1) time

• Heaps are mainly used to implement priority queues.

---

🎯 Quick Example of Max-Heap

Suppose we insert: 40, 20, 30, 35, 25, 80, 32

Step-by-Step Insertions

🔹 Insert 40

Heap:

40

---

🔹 Insert 20

     40
    /
   20

✔ Heap property holds.

---

🔹 Insert 30

     40
    /  \
   20   30

✔ Heap property holds.

---

🔹 Insert 35

Insert at next available spot (left child of 20):

       40
      /  \
    20    30
   /
  35

Now compare with parent 20 → 35 > 20 → swap.

       40
      /  \
    35    30
   /
  20

✔ Heap property holds.

---

🔹 Insert 25

Insert at right child of 35:

       40
      /  \
    35    30
   / \
  20 25

Parent 35 ≥ 25 → no swap needed.

---

🔹 Insert 80

Insert at left child of 30:

       40
      /  \
    35    30
   / \   /
 20  25 80

Compare 80 > 30 → swap:

       40
      /  \
    35    80
   / \   /
 20  25 30

Now compare 80 > 40 → swap again:

       80
      /  \
    35    40
   / \   /
 20  25 30

✔ Heap property restored.

---

🔹 Insert 32

Insert at right child of 40:

       80
      /  \
    35    40
   / \   / \
 20  25 30 32

Parent 40 ≥ 32 → ✔ heap property holds.

---

✅ Final Max Heap after all insertions:

       80
      /  \
    35    40
   / \   / \
 20  25 30 32

• 80 is at the root (largest element).

✅ Final Max Heap (Array Representation)

Index:   0  1    2  3    4   5   6
Value: [80, 35, 40, 20, 25, 30, 32]

---

✨ Summary Table

Operation	Description	Time Complexity
Insert	Add element at end and heapify up	O(log n)
Delete (Root)	Replace root with last element and heapify down	O(log n)
Build Heap	Create a heap from an unsorted array	O(n)
Find Max/Min	Return root element (no changes needed)	O(1)

✨ C Program - Binary Heap

#include <stdio.h>

#define MAX 100

int heap[MAX];

int size = -1;

void swap(int *a, int *b) {

    int temp = *a;

    *a = *b;

    *b = temp;

}

void insert(int value) {

    if (size >= MAX - 1) {

        printf("Heap is full!\n");

        return;

    }

    size++;

    heap[size] = value;

    int current = size;

    while (current > 0 && heap[(current - 1) / 2] < heap[current]) {

        swap(&heap[current], &heap[(current - 1) / 2]);

        current = (current - 1) / 2;

    }

}

void heapifyDown(int index) {

    int largest = index;

    int left = 2 * index + 1;

    int right = 2 * index + 2;

    if (left <= size && heap[left] > heap[largest])

        largest = left;

    if (right <= size && heap[right] > heap[largest])

        largest = right;

    if (largest != index) {

        swap(&heap[index], &heap[largest]);

        heapifyDown(largest);

    }

}

int deleteRoot() {

    if (size < 0) {

        printf("Heap is empty!\n");

        return -1;

    }

    int root = heap[0];

    heap[0] = heap[size];

    size--;

    heapifyDown(0);

    return root;

}

void display() {

    if (size < 0) {

        printf("Heap is empty!\n");

        return;

    }

    printf("Heap elements: ");

    for (int i = 0; i <= size; i++) {

        printf("%d ", heap[i]);

    }

    printf("\n");

}

int main() {

    int choice, value;

    while (1) {

        printf("\n--- Binary Heap Operations ---\n");

        printf("1. Insert\n2. Delete Root\n3. Display\n4. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter value to insert: ");

                scanf("%d", &value);

                insert(value);

                break;

            case 2:

                value = deleteRoot();

                if (value != -1)

                    printf("Deleted root: %d\n", value);

                break;

            case 3:

                display();

                break;

            case 4:

                printf("Exiting...\n");

                return 0;

            default:

                printf("Invalid choice!\n");

        }

    }

}

🛡️ Important Points:

• Insert: Add at the end and heapify up (O(log n))

• Delete Root: Replace root with last, heapify down (O(log n))

• Display: Just traverse array

---

🔥 Summary

With these simple algorithms:

• You can build a heap.

• Insert elements dynamically.

• Delete the root (max or min value depending on the heap).

• View the heap structure any time.