What is Min Heap: Definition, Example, and Uses

A min heap is a special tree-based data structure where the smallest element is always at the root. Each parent node is less than or equal to its child nodes, ensuring quick access to the minimum value.

How It Works

A min heap organizes data in a way that the smallest value is always easy to find, sitting at the top (root) of the structure. Imagine a pyramid where each block is smaller than the blocks below it. This means if you look at any block, it will never be bigger than the blocks it supports.

When you add or remove elements, the heap rearranges itself to keep this order. This process is like sorting a stack of books so the smallest book is always on top, making it quick to grab the smallest one without searching through all books.

Example

This example shows how to create a min heap, add elements, and get the smallest element using Python's heapq module.

python

import heapq

min_heap = []
heapq.heappush(min_heap, 20)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 15)
heapq.heappush(min_heap, 10)

smallest = heapq.heappop(min_heap)
print(f"Smallest element: {smallest}")

Output

Smallest element: 5

When to Use

Use a min heap when you need quick access to the smallest item in a collection, especially if the collection changes often. It is useful in tasks like:

• Finding the smallest element repeatedly without sorting the entire list.
• Implementing priority queues where the highest priority is the smallest value.
• Algorithms like Dijkstra's shortest path or Huffman coding that rely on efficiently picking the smallest element.

Key Points

• A min heap always keeps the smallest element at the root.
• It is a complete binary tree, meaning all levels are fully filled except possibly the last.
• Insertion and removal keep the heap property by rearranging elements.
• Min heaps are efficient for priority queue operations.

Key Takeaways

A min heap keeps the smallest element at the root for quick access.

It is a complete binary tree with a special ordering property.

Min heaps efficiently support insertion and removal while maintaining order.

They are ideal for priority queues and algorithms needing fast minimum retrieval.