What Is a Min Heap?
Explore min heaps as complete binary trees where the smallest element is always at the root. Learn to implement key operations such as insert, extract min, peek, and size using JavaScript. Understand the array representation, bubbling techniques, and time complexity to apply min heaps in tasks like priority queues and graph algorithms.
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, meaning the smallest element in the entire heap is always sitting at the root and is instantly accessible at any time.
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 whom are greater than 2. Similarly, 5's children are 10 and 14, both of whom 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:
...