What is Min Heap?

Min Heap is a type of binary heap where the key at the root must be the minimum among all keys present in the binary heap. The same property must be recursively true for all nodes in the binary tree.

Min Heap Definition:

Min Heap is a complete binary tree, where value of each node is smaller than or equal to the values of its children. Therefore, Min Heap stores the minimum value at the root of the heap. Min Heap is used to maintain the minimum element in a collection of data.

Properties of Min Heap:

• Binary Tree Structure: A Min Heap is a complete binary tree, meaning all the levels are filled completely, except possibly the last level, which is filled left to right.
• Heap Property: The value of each node is greater than or equal to its parent, with the minimum value at the root.

Structure of Min Heap:

• Complete Binary Tree: A Min Heap is represented as a complete binary tree. Each level is fully filled before moving on to the next level, and all nodes are as far left as possible.
• Array Representation: Min Heaps are often implemented using arrays. For a node at index i, its left child is at index 2*i + 1, its right child is at index 2*i + 2, and its parent is at index (i-1) / 2.

Applications of Min-Heap:

• Priority Queue: Min Heaps are used to implement priority queues, where the element with the highest priority(minimum value) is present at the root of the heap.
• Dijkstra’s Algorithm: Dijkstra’s algorithm is a shortest path algorithm that finds the shortest path between two nodes in a graph. A min heap can be used to keep track of the unvisited nodes with the smallest distance from the source node.
• Sorting: A min heap can be used as a sorting algorithm to efficiently sort a collection of elements in ascending order.
• Finding the median: A min heap can be used to efficiently find the median of a stream of numbers. We can use one min heap to store the larger half of the numbers and one max heap to store the smaller half. The median will be the root of the min heap.

Advantages of Min Heap:

• Efficient Insertions and Deletions: Both insertion and deletion operations have a time complexity of O(logn), making them efficient.
• Easy Access to Minimum Element: The minimum element is always at the root, making access O(1).

Disadvantages of Min Heap:

• Inefficient Searching: Min Heap does not allow searching for a specific element and may require to visit all the elements in the worst case.
• Not a stable data structure: Min Heap is not a stable data structure so the relative order of equal elements may not be preserved

Min Heap is a data structure that maintains a dynamic set of elements, supporting quick retrieval and removal of the minimum element. Understanding and utilizing Min Heaps can significantly optimize performance in relevant algorithms and systems.