Solve problems that are commonly asked in C++ coding interviews related to common data structures.

Ace the C++ Coding Interview

Data structures are among the fundamentals of computer science and are often a core decision in developing efficient programs. They are categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This module contains a detailed review of common data structures in C++. We'll also become well-equipped with different data structures by implementing them.
By the end of this module, we'll have expertise in solving problems in data structures.

Data Structures

# Implementation

Now that we have discussed all the functions of a Min-Heap, we've implemented them in the following code executable. Run and test the code on multiple outputs to see if it returns the elements in the correct order every time. Try it!

#include <iostream>
#include <vector>
using namespace std;

template <typename T>

class MinHeap{
  private:
  vector<T> h;
  
  inline int parent(int i){
    return (i-1)/2;
  }
  inline int lchild(int i){
    return i*2 + 1;
  }
  inline int rchild(int i){
    return i*2 + 2;
  }
  
  void minHeapify(int i){
    int lc = lchild(i);
    int rc = rchild(i);
    int imin = i;
    
    if(lc < size()  &&  h[lc] < h[imin])
      imin = lc;
    if(rc < size()  &&  h[rc] < h[imin])
      imin = rc;
    if(i != imin){
      swap(h[i], h[imin]);
      minHeapify(imin);
    }
  }
  
  //percolateUp(): It is meant to restore the 
  //heap property going up from a node to the root.
  void percolateUp(int i){
    if(i <= 0)
      return;
    else if(h[parent(i)] > h[i]){
      swap(h[i], h[parent(i)]);
      percolateUp(parent(i));
    }
  }
  
  public:
  
  MinHeap(){
    h.resize(0); 
  }
  
  int size(){
    return h.size();
  }
  
  T getMin(){
    if (size() <= 0){
      return -1;
    }
    else{
    return h[0];
    }
  }
  
  void insert (const T &key){
    h.push_back(key);
    int i = size()-1;
    
    percolateUp(i);
  }
  
  void removeMin(){
    if (size() == 1){
       h.pop_back();
    }
    else if(size() > 1){
      swap(h[0], h[size()-1]);
      h.pop_back();
      minHeapify(0);
    }
    else
      return;
  }
  
  void buildHeap(T arr[], int size){
       // Copy elements of array into vector h 
      copy(&arr[0], &arr[size], back_inserter(h));
      for (int i = (size - 1)/2; i >= 0; i--){
        minHeapify(i);
      }
    }
  //Bonus function: printHeap()
  void printHeap(){
    for(int i = 0; i <= size()-1; i++){
      cout << h[i] << " ";
    }
    cout << endl;
  }
};

#include "MinHeap.h"

int main() {
  MinHeap<int> heap;

  int size = 6;
  int arr[size] = {2,8,15,5,1,20};

  heap.buildHeap(arr,size);
  heap.printHeap();
  
  
  cout << heap.getMin() << endl;
  heap.removeMin();
  cout << heap.getMin() << endl;
  heap.removeMin();
  
  heap.insert(-10);
  cout << heap.getMin() << endl;
  
  return 0;
}

## Explanation
The code above for min heaps is an exact reflection of the code for max heaps! It's a good exercise to try and figure out what changed. However, if you have any confusion about it, leave a question on the community forum, and we'll get back to you!

The overall time complexity of building the Heap in a Min Heap is the same as the Max Heap: $O(n)$. You can refer to [Max Heap (Implementation)](https://www.educative.io/courses/data-structures-coding-interviews-cpp/max-heap-implementation) for the complete calculation.




We'll implement a min heap in this lesson.

Min Heap (Implementation)

Implementation