Min Heap in C++

Min Heap is a special type of data structure, which is a complete binary tree that follows the following two properties: 

1. All nodes in the Min Heap are greater than or equal to their children. 
2. The root node of the Min Heap is the minimum of all nodes. 

Min Heap is a common data structure used in many algorithms such as heapsort, priority queues, and graph algorithms. It is also used to implement efficient priority queues. This article will discuss the tree structure of Min Heap, time complexity of access, search, insertion, and deletion, as well as the space complexity of Min Heap in C++. 

Tree Structure of Min Heap 

A Min Heap is a complete binary tree, meaning it is a binary tree in which all levels are filled except for the last level and all nodes are as far left as possible. The root node of a Min Heap is the minimum of all nodes, and all nodes in the Min Heap are greater than or equal to their children. In the following example of a Min Heap, the root node is 4, and all of its children (2 and 6) are greater than or equal to it. 

int MinHeap[7] = {4, 2, 6, 1, 3, 5, 7};

Time Complexity 

The time complexity of access, search, insertion, and deletion in a Min Heap is as follows: 

• Access: The time complexity of access in a Min Heap is O(1), as we can directly access the root node which is the minimum. 
• Search: The time complexity of search in a Min Heap is O(n), as we need to traverse the tree to find the element we are searching for. 
• Insertion: The time complexity of insertion in a Min Heap is O(log n), as we need to insert the new element in the correct position in the heap. 
• Deletion: The time complexity of deletion in a Min Heap is O(log n), as we need to delete the element from the heap and rearrange the elements accordingly. 

Space Complexity 

The space complexity of a Min Heap is O(n), as we need to store all of the nodes in the heap. 

C++ Implementation 

We can implement a Min Heap in C++ using an array. We can use the following code to create a Min Heap of size 7. 

// create an array of size 7 
int MinHeap[7]; 

// insert elements into the array 
MinHeap[0] = 4; 
MinHeap[1] = 2; 
MinHeap[2] = 6; 
MinHeap[3] = 1; 
MinHeap[4] = 3; 
MinHeap[5] = 5; 
MinHeap[6] = 7; 

// create a function to heapify the array 
void heapify(int MinHeap[], int n, int i) 
{ 
    int smallest = i; // root 
    int l = 2*i + 1; // left child 
    int r = 2*i + 2; // right child 
  
    // if left child is smaller than root 
    if (l < n && MinHeap[l] < MinHeap[smallest]) 
        smallest = l; 
  
    // if right child is smaller than root 
    if (r < n && MinHeap[r] < MinHeap[smallest]) 
        smallest = r; 
  
    // if root is not smallest 
    if (smallest != i) 
    { 
        swap(MinHeap[i], MinHeap[smallest]); 
  
        // heapify the root 
        heapify(MinHeap, n, smallest); 
    } 
} 

// create a function to build the Min Heap 
void buildMinHeap(int MinHeap[], int n) 
{ 
    // build the heap from the bottom up 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(MinHeap, n, i); 
} 

Conclusion

In conclusion, Min Heap is a special type of data structure that is used in many algorithms. It is a complete binary tree in which all nodes are greater than or equal to their children, and the root node is the minimum of all nodes. The time complexity of access, search, insertion, and deletion in a Min Heap is O(1), O(n), O(log n), and O(log n) respectively. The space complexity of Min Heap is O(n). Min Heap can be implemented in C++ using an array.

Exercises

// function to insert an element into a Min Heap 
void insert(int MinHeap[], int n, int x) 
{ 
    // insert the element at the end of the heap 
    MinHeap[n] = x; 
  
    // heapify the root node 
    int i = n; 
    while (i != 0 && MinHeap[(i - 1)/2] > MinHeap[i]) 
    { 
        swap(MinHeap[(i - 1)/2], MinHeap[i]); 
        i = (i - 1) / 2; 
    } 
} 

// function to delete an element from a Min Heap 
void deleteElement(int MinHeap[], int n, int x) 
{ 
    // find the element to be deleted 
    int i; 
    for (i = 0; i < n; i++) 
        if (MinHeap[i] == x) 
            break; 
  
    // replace the element to be deleted with the last element in the heap 
    swap(MinHeap[i], MinHeap[n - 1]); 
  
    // heapify the root node 
    i = 0; 
    while (i < n - 1 && MinHeap[i] > MinHeap[2*i + 1]) 
    { 
        swap(MinHeap[i], MinHeap[2*i + 1]); 
        i = 2*i + 1; 
    } 
} 

// function to sort a Min Heap 
void heapSort(int MinHeap[], int n) 
{ 
    // build the heap from the bottom up 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(MinHeap, n, i); 
  
    // sort the heap 
    for (int i = n - 1; i >= 0; i--) 
    { 
        // move the root node to the end 
        swap(MinHeap[i], MinHeap[0]); 
  
        // heapify the root node 
        heapify(MinHeap, i, 0); 
    } 
} 

// function to find the minimum element in a Min Heap 
int minElement(int MinHeap[], int n) 
{ 
    // the root node is the minimum element 
    return MinHeap[0]; 
} 

// function to search for an element in a Min Heap 
bool searchElement(int MinHeap[], int n, int x) 
{ 
    // traverse the heap to search for the element 
    for (int i = 0; i < n; i++) 
    { 
        if (MinHeap[i] == x) 
            return true; 
    } 
    return false; 
}