Min Heap In Data Structure Using C++

on

Data Structure Using C++

Heap Data Structure

Min Heap

class minHeap{
 private:
  int capacity;
  int size;
  int *arr;
  int getLeftChildIndex(int parentIndex){
   return 2 * parentIndex+1;
  }
  int getRightChildIndex(int parentIndex){
   return 2 * parentIndex+2;
  }
  int getParentIndex(int childIndex){
   return (childIndex-1)/2;
  }
  bool hasLeftChild(int index){
   return getLeftChildIndex(index) < size;
  }
  bool hasRightChild(int index){
   return getRightChildIndex(index) < size;
  }
  bool hasParent(int index){
   return getParentIndex(index) >= 0;
  }
  int leftChild(int index){
   return arr[getLeftChildIndex(index)];
  }
  int rightChild(int index){
   return arr[getRightChildIndex(index)];
  }
  int parent(int index){
   return arr[getParentIndex(index)];
  }
  void swap(int x, int y){
   int temp=arr[x];
   arr[x]=arr[y];
   arr[y]=temp;
  }
 public:
  minHeap(int c);
  int peek();
  int remove();
  int remove(int index);
  void add(int element);
  void heapifyUp();
  void heapifyDown(int index);
};
minHeap::minHeap(int c){
 capacity=c;
 arr=new int[capacity];
 size=0;
}
int minHeap::peek(){
 if(size>0){
  return arr[0];
 }
}
void minHeap::add(int element){
 if(size<capacity){
  arr[size]=element;
  size++;
  heapifyUp();
 }
}
int minHeap::remove(){
 if(size>0){
  int element=arr[0];
  arr[0]=arr[size-1];
  size--;
  heapifyDown(0);
  return element;
 }
}
int minHeap::remove(int index){
 if(index<size){
  int element=arr[index];
  arr[index]=arr[size-1];
  size--;
  heapifyDown(index);
  return element;
 }else{
  cout<<"Index not found!"<<endl;
  return 0;
 }
}
void minHeap::heapifyUp(){
 int index=size-1;
 while(hasParent(index)&&parent(index)>arr[index]){
  swap(getParentIndex(index),index);
  index=getParentIndex(index);
 }
}
void minHeap::heapifyDown(int index){
 while(hasLeftChild(index)){
  int smallerChildIndex=getLeftChildIndex(index);
  if(hasRightChild(index)&&rightChild(index)<leftChild(index)){
   smallerChildIndex=getRightChildIndex(index);
  }
  if(arr[index]<arr[smallerChildIndex]){
   break;
  }else{
   swap(index, smallerChildIndex);
  }
  index=smallerChildIndex;
 }
}
int main(){
 minHeap h(5);
 h.add(3);
 h.add(6);
 h.add(1);
 h.add(8);
 h.add(2);
 cout<<h.remove()<<endl;
 h.add(5);
 cout<<h.peek()<<endl;
 cout<<h.remove(4)<<endl;
}

Let me know in the comment section if you have any question.

Previous Post:
String Binary Search Tree In Data Structure Using C++

Comments

Post a Comment