min heap

A min heap is a tree-based data structure in which every parent node holds a value less than or equal to the values of its children, so the smallest element always sits at the root. It’s the mirror image of a max heap, whose root holds the largest element instead.

A min heap is a complete binary tree, meaning every level is full except possibly the last, which fills from left to right. That regular shape lets the heap live in a plain array without pointers, where the children of the node at index i sit at positions 2i + 1 and 2i + 2 and its parent at (i - 1) // 2.

The heap property is local, so each parent stays ordered against its own children while siblings and separate branches remain unordered.

Inserting a value appends it to the end and sifts it up past larger parents, and removing the minimum takes the root, moves the last element into its place, and sifts it down past its smaller child. These operations carry costs bounded by the tree’s height:

• Find-min (peek): O(1), because the minimum is always the root
• Insert (push): O(log n) in the worst case
• Extract-min (pop): O(log n) in the worst case

To see how those operations reshape the heap, work through the visualization below: insert a value to watch it sift up, extract the minimum to watch the last element take the root and sift down, and select any node to see how its array index maps to its parent and children.

Surfacing the smallest item cheaply makes the min heap the usual backing structure for a priority queue and a building block in algorithms such as Dijkstra’s algorithm and heapsort.

Related Resources

Tutorial

The Python heapq Module: Using Heaps and Priority Queues

In this step-by-step tutorial, you'll explore the heap and priority queue data structures. You'll learn what kinds of problems heaps and priority queues are useful for and how you can use the Python heapq module to solve them.

intermediate data-structures python stdlib

For additional information on related topics, take a look at the following resources:

• Python Stacks, Queues, and Priority Queues in Practice (Tutorial)
• Sorting Algorithms in Python (Tutorial)
• Common Python Data Structures (Guide) (Tutorial)
• Python's deque: Implement Efficient Queues and Stacks (Tutorial)
• Introduction to Sorting Algorithms in Python (Course)
• Stacks and Queues: Selecting the Ideal Data Structure (Course)
• Python Stacks, Queues, and Priority Queues in Practice (Quiz)
• Records and Sets: Selecting the Ideal Data Structure (Course)
• Dictionaries and Arrays: Selecting the Ideal Data Structure (Course)
• Common Python Data Structures (Guide) (Quiz)
• Working With Python's deque (Course)
• Python's deque: Implement Efficient Queues and Stacks (Quiz)