Priority Queue Using Heap In Data Structure Using C++

Data Structure Using C++

Heap Data Structure

Priority Queue | Max Heap

Priority Queue Using Heap In C++

const int MAX_SIZE=10;
class maxHeap{
 private:
  int capacity;
  int size;
  int arr[MAX_SIZE][2];
  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)][0];
  }
  int rightChild(int index){
   return arr[getRightChildIndex(index)][0];
  }
  int parent(int index){
   return arr[getParentIndex(index)][0];
  }
  void swap(int x, int y){
   int p=arr[x][0];
   int d=arr[x][1];
   arr[x][0]=arr[y][0];
   arr[x][1]=arr[y][1];
   arr[y][0]=p;
   arr[y][1]=d;
  }
 public:
  maxHeap();
  void add(int priority,int element);
  int peek();
  int remove();
  int remove(int index);
  void heapifyUp();
  void heapifyDown(int index);
  int isFull(){
   return size==capacity-1;
  }
  int isEmpty(){
   return size==0;
  }
};
maxHeap::maxHeap(){
 capacity=MAX_SIZE;
 size=0;
}
int maxHeap::peek(){
 if(size>0){
  return arr[0][1];
 }
}
void maxHeap::add(int priority,int element){
 if(size<capacity){
  arr[size][0]=priority;
  arr[size][1]=element;
  size++;
  heapifyUp();
 }
}
int maxHeap::remove(){
 if(size>0){
  int element=arr[0][1];
  arr[0][0]=arr[size-1][0];
  arr[0][1]=arr[size-1][1];
  size--;
  heapifyDown(0);
  return element;
 }else{
  cout<<"Index not found!"<<endl;
  return 0;
 }
}
int maxHeap::remove(int index){
 if(index<size){
  int element=arr[index][1];
  arr[index][0]=arr[size-1][0];
  arr[index][1]=arr[size-1][1];
  size--;
  heapifyDown(index);
  return element;
 }else{
  cout<<"Index not found!"<<endl;
  return 0;
 }
}
void maxHeap::heapifyUp(){
 int index=size-1;
 while(hasParent(index)&&parent(index)<arr[index][0]){
  swap(getParentIndex(index),index);
  index=getParentIndex(index);
 }
}
void maxHeap::heapifyDown(int index){
 while(hasLeftChild(index)){
  int greaterChildIndex=getLeftChildIndex(index);
  if(hasRightChild(index)&&rightChild(index)>leftChild(index)){
   greaterChildIndex=getRightChildIndex(index);
  }
  if(arr[index][0]>arr[greaterChildIndex][0]){
   break;
  }else{
   swap(index, greaterChildIndex);
  }
  index=greaterChildIndex;
 }
}class PriorityQueue 
{
 private:
  maxHeap *heap;
 public:
  PriorityQueue() 
  {
   heap = new maxHeap();
  };
  ~PriorityQueue() 
  {
        delete heap;
  };
  void enqueue(int p,int val) 
  {
   if(!heap->isFull()) 
   {
    heap->add(p,val);
   }else
   {
   cout << "insert queue is full." << endl;
   }   
  };
  int dequeue()
  {
   if(!heap->isEmpty()) 
   {
             int val=heap->remove(); 
    return val;
   }
   cout << "remove - queue is empty." << endl;
   return NULL;
  };
  bool isEmpty(){
   return heap->isEmpty();
  }
  bool isFull (){
   heap->isFull();
  }
  int getFront(){
   if(!isEmpty()){
    int val=heap->peek();
    return val;
   }
   else{
    return NULL;
   }
  }
}; 
int main(){
 PriorityQueue q;
 q.dequeue();
 q.enqueue(2,1);
 q.enqueue(3,3);
 q.enqueue(1,4);
 cout<<"Front element is:"<<q.getFront()<<endl;
 cout<<"Remove:"<<q.dequeue()<<endl;
 cout<<"Remove:"<<q.dequeue()<<endl;
 cout<<"Remove:"<<q.dequeue()<<endl;
 cout<<"Remove:"<<q.dequeue()<<endl;
}

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

Previous Post:
Heap Sort In Data Structure Using C++

Next Post:

Linear Search | Sequential Search In Data Structure Using C++