How do you implement a min heap?

A min heap is implemented by using a binary tree structure and maintaining the heap property during insertions and deletions.

A min heap is a complete binary tree where each node is smaller than or equal to its children. This property is called the heap property. The root of the tree contains the smallest element, and this is the key feature of a min heap.

To implement a min heap, you can use an array where each element represents a node of the binary tree. The parent-child relationship can be defined using indices. For a node at index i, its left child is at index 2i+1 and its right child is at index 2i+2. Conversely, for a node at index i, its parent is at index (i-1)/2.

When inserting a new element, you add it at the end of the array (or the next available spot in the binary tree), and then "bubble up" the element to its correct position to maintain the heap property. Bubbling up involves swapping the new element with its parent if the parent is larger. This process continues until the new element is smaller than its parent or it becomes the root.

When deleting the minimum element (the root), you replace the root with the last element in the array (or the last node in the tree), and then "bubble down" this element to its correct position. Bubbling down involves swapping the element with its smallest child if the element is larger than the child. This process continues until the element is smaller than its children or it becomes a leaf.

Building a min heap from an array of n elements can be done in O(n) time, while operations like insert, delete min, and decrease key can be done in O(log n) time. This makes min heaps efficient for algorithms that need to repeatedly find and remove the smallest element, like Dijkstra's algorithm or the heap sort algorithm.

Remember, the key to implementing a min heap is maintaining the heap property during insertions and deletions. This ensures that the root always contains the smallest element, which can be accessed in constant time.