What Is a Min Heap?
Explore the structure and functionality of a min heap, a complete binary tree where the parent node is always smaller than its children. Understand key operations such as insert, extract min, peek, and size, along with their C# implementations and time complexities. This lesson helps you grasp how min heaps maintain efficient access to the smallest element, useful for priority queues and algorithms like Dijkstra’s.
We'll cover the following...
Min heap
A min heap is a complete binary tree where every parent node is smaller than or equal to its children. This means the smallest element in the entire heap is always at the root and can be accessed immediately.
Example: Consider a min heap containing the values: [2, 5, 8, 10, 14].
The root is 2 because it is the smallest element. Its children are 5 and 8, both of which are greater than 2. Similarly, 5's children are 10 and 14, both of which are greater than 5. This ordering holds at every level of the tree, which makes it a valid min heap.
In array form, this heap is stored as [2, 5, 8, 10, 14], with the root at index 0.
Understanding the index formulas
For any element at index i, its parent and children can be located using simple arithmetic:
Parent:
Left child:
Right child:
...