Heap — Data Structures

🌱 What Is a Heap?

A Heap is a special kind of binary tree that follows two important rules:

1. It’s a complete binary tree
   → That means all levels are completely filled except possibly the last one, which is filled from left to right.
2. It follows the heap property
   → The value of each node is related to its children in a specific way — either greater (for Max Heap) or smaller (for Min Heap).

So, in short:
➡️ A heap is a binary tree that is complete and obeys the heap rule.

---

🌿 Two Types of Heaps

1. Max Heap

In a Max Heap, the value of every parent node is greater than or equal to the values of its children.
In simple words — the largest element is always at the root.

Example:

          50
         /  \
       30    40
      / \    /
    10  20  35

Here:

• 50 > 30, 40
• 30 > 10, 20
• 40 > 35

So, it follows the Max Heap rule — every parent is bigger than its children.

---

2. Min Heap

In a Min Heap, the value of every parent node is smaller than or equal to the values of its children.
So, the smallest element is always at the root.

Example:

          10
         /  \
       20    15
      / \    /
    30  40  25

Here:

• 10 < 20, 15
• 20 < 30, 40
• 15 < 25

Everything fits perfectly — the smallest number sits at the top!

---

🌸 Heap Properties (In Simple Words)

Let’s make sure these rules stick in your mind 👇

Property	Meaning
Shape Property	The tree is complete — no gaps, filled from left to right.
Heap Property	For Max Heap → parent ≥ children; For Min Heap → parent ≤ children.
Root Node	Always the largest (Max Heap) or smallest (Min Heap).

---

🌼 Real-Life Analogy

Think of a heap like a tournament ladder.
In a Max Heap, the strongest player keeps winning and stays at the top.
Even though there might be smaller players below, the champion (maximum value) remains at the root.

In a Min Heap, it’s the opposite — imagine a race for the lowest score.
The smallest number (best score) stays right on top.

---

🌺 Representing a Heap in Memory

Heaps are usually stored not as linked nodes but as arrays, because they’re complete binary trees.
We can easily map parent-child relationships using index numbers.

For a node at index i:

• Left child → 2*i
• Right child → 2*i + 1
• Parent → i / 2 (integer division)

Example (Max Heap stored as array):

Tree:
          50
         /  \
       30    40
      / \    /
    10  20  35

Array Representation:
[50, 30, 40, 10, 20, 35]

Let’s check:

• 30 and 40 are children of 50 → ✅
• 10 and 20 are children of 30 → ✅
• 35 is left child of 40 → ✅

Everything matches perfectly!

---

🌻 Basic Heap Operations

Let’s look at what we can do with a heap.

1. Insertion

When we insert a new element:

1. Place it in the next available spot (to keep the tree complete).
2. Then “heapify” — move it up or down until the heap property is satisfied.

Example (Max Heap):
Insert 45 → placed below, then compared upward:

Before:
          50
         /  \
       30    40
      / \    /
    10  20  35

Insert 45 → temporarily below 40:
          50
         /  \
       30    40
      / \    / \
    10  20  35  45

Now compare:
45 > 40 → swap!

After heapifying:

          50
         /  \
       30    45
      / \    / \
    10  20  35  40

---

2. Deletion (Removing Root)

Usually, we remove the root element (largest or smallest).
Steps:

1. Replace root with the last element.
2. Remove the last node.
3. “Heapify” down — keep swapping until the heap property holds again.

---

3. Heapify

“Heapify” simply means adjusting the tree to make sure the heap rule is followed.
It’s like cleaning up your desk — you move things around until everything’s back in its proper place. 🧹

---

4. Heap Sort

One of the most popular uses of heaps is Heap Sort — a powerful sorting algorithm.

How it works:

1. Build a Max Heap.
2. The root (largest element) goes to the end of the array.
3. Reduce heap size and heapify again.
4. Repeat until sorted.

Result: A perfectly sorted list! ✨

---

🌷 Applications of Heaps

Heaps are incredibly useful in computer science.
Here are a few real-world uses:

Application	Description
Heap Sort	Sorting algorithm based on heap property.
Priority Queue	Elements with higher priority are processed first.
Graph Algorithms	Used in Dijkstra’s and Prim’s algorithms for finding shortest paths and minimum spanning trees.
Scheduling Systems	Helps pick the next task with the highest priority.

---

🌻 Diagram – Max Heap and Min Heap

Max Heap:                   Min Heap:
     50                         10
    /  \                       /  \
  30    40                   20    15
 / \    /                   / \    /
10 20  35                 30 40  25

---

🌼 Quick Comparison

Feature	Max Heap	Min Heap
Root Node	Largest element	Smallest element
Order	Parent ≥ Children	Parent ≤ Children
Use Case	Heap Sort (Descending)	Heap Sort (Ascending)
Common Use	Priority queues	Scheduling, shortest path algorithms

---