Learn how heaps work, how to implement them using arrays, and where they are used in real-world applications — with diagrams and Python code examples!

📌 Table of Contents

1. What is a Heap?
2. Types of Heap
3. Heap as a Complete Binary Tree
4. Array Representation of a Heap
5. Core Operations
6. Python Implementation
   • Min-Heap
   • Max-Heap
7. Time Complexity
8. Real-World Applications
9. Summary

🔍 What is a Heap?

A heap is a special tree-based data structure that satisfies the heap property:

• Min-Heap: Parent is less than or equal to children.
• Max-Heap: Parent is greater than or equal to children.

✅ It is always a complete binary tree, meaning every level is fully filled except possibly the last, and the last level is filled from left to right.

📂 Types of Heap

📸 Visual of Min-Heap

     1
   /  \
  3    5
/   \
7    9

📸 Visual of Max-Heap

    9
  /   \
 6     5
/ \
2   3

🌲 Heap as a Complete Binary Tree

• Every level is completely filled except possibly the last.
• The last level is filled from left to right.

🧮 Array Representation of a Heap

In a 0-indexed array, for a node at index i:

• Left Child → 2 * i + 1
• Right Child → 2 * i + 2
• Parent → (i - 1) // 2

⚙️ Core Operations

✅ Insert

• Add element at the end of the array.
• Bubble up (heapify-up) to restore heap property.

✅ Extract Min/Max

• Replace root with last element.
• Remove the last element.
• Bubble down (heapify-down) to restore heap property.

🧑‍💻 Min-Heap Implementation

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i): return (i - 1) // 2
    def left(self, i): return 2 * i + 1
    def right(self, i): return 2 * i + 2

    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extract_min(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def _heapify_down(self, i):
        smallest = i
        left = self.left(i)
        right = self.right(i)

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right

        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._heapify_down(smallest)

    def display(self):
        print("Min-Heap:", self.heap)

🧑‍💻 Max-Heap Implementation

class MaxHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i): return (i - 1) // 2
    def left(self, i): return 2 * i + 1
    def right(self, i): return 2 * i + 2

    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extract_max(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def _heapify_down(self, i):
        largest = i
        left = self.left(i)
        right = self.right(i)

        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right

        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self._heapify_down(largest)

    def display(self):
        print("Max-Heap:", self.heap)

⏱️ Time Complexity

📈 Real-World Applications

• ✅ Priority Queues
• 📅 Job/Task Scheduling
• 🚦 Dijkstra’s Algorithm
• 📊 Dynamic Median Finding
• 🧮 Heap Sort Algorithm

✅ Summary