Min Heap

A Min-Heap is a specific type of binary heap (priority queue) where the key or value of the parent node is always less than or equal to that of the child nodes. This means that the smallest value in the Min-Heap is always at the root (the topmost node). Min-Heaps have the following properties:

1. Complete Binary Tree: A Min-Heap is a completely filled binary tree, meaning all levels are fully filled except possibly for the last level, which is filled from left to right.

2. Heap Property: For every node $i$ with child nodes $2i+1$ (left) and $2i+2$ (right), the value of the parent node $i$ is less than or equal to the values of the child nodes. Mathematically: $A[i]\le A[2i+1]$ and $A[i]\le A[2i+2]$, if these child nodes exist.

Uses of Min-Heaps

Min-Heaps are often used in algorithms that repeatedly extract the smallest element from a set. Here are some common applications:

1. Priority Queue: Min-Heaps are used to implement priority queues, where the element with the highest priority (in this case, the smallest value) is always at the top.

2. Heapsort: The Heapsort algorithm can be implemented with Min-Heaps or Max-Heaps. With a Min-Heap, the smallest element is repeatedly extracted to produce a sorted list.

3. Graph Algorithms: Min-Heaps are used in graph algorithms like Dijkstra's algorithm for finding the shortest paths and Prim's algorithm for finding minimum spanning trees.

Basic Operations on a Min-Heap

The basic operations that can be performed on a Min-Heap include:

1. Insert: A new element is added at the last position and then moved up (Bubble-Up) to restore the heap property.

2. Extract-Min: The root element (the smallest element) is removed and replaced by the last element. This element is then moved down (Bubble-Down) to restore the heap property.

3. Get-Min: The root element is returned without removing it. This has a time complexity of $O(1)$.

4. Heapify: This operation restores the heap property when it is violated. There are two variants: Heapify-Up and Heapify-Down.

Example

Suppose we have the following elements: [3, 1, 6, 5, 2, 4]. A Min-Heap representing these elements might look like this:

       1
     /   \
    2     4
   / \   /
  5   3 6

Here, 1 is the root of the heap and the smallest element. Every parent node has a value less than or equal to the values of its child nodes.

In summary, a Min-Heap is an efficient data structure for managing datasets where the smallest element needs to be repeatedly accessed and removed.