Min Heap

Definition

A Min Heap is the exact opposite of a Max Heap. In a Min Heap, the value of every parent node is less than or equal to the values of its children. The smallest number is always at the root.

How it Works

1. The Rule: Every parent must be smaller than its children.
2. The Root: The top-most element is always the absolute minimum value in the entire dataset.

Example

Input Numbers: [10, 20, 15, 30, 40]

Min Heap Structure:

      10
    /  \
  20    15
  /  \
30    40

Notice that 10 is smaller than 20 and 15. 20 is smaller than 30 and 40.

Code Example (Python)

Python

import heapq

# Python’s default heap implementation is a Min Heap
min_heap = []
numbers = [40, 30, 15, 10, 20]

# Build the heap
for num in numbers:
    heapq.heappush(min_heap, num)

# The smallest element is always at index 0
print(“Smallest value:”, min_heap[0]) # Output: 10

# Remove the smallest element
smallest = heapq.heappop(min_heap)
print(“Removed:”, smallest) # Output: 10

Use Cases

• Merging Sorted Arrays: Efficiently combining multiple sorted lists into one.
• Real-time Stream Data: Finding the median of a number stream dynamically.