Question

I need to make pseudo code for hybrid priority queue using both minheap and maxheap by ARRAY.
i need to have a function that extends the size of array once it meets certain condition.

Also, I need to implement function remove, insert(k,v), top, toggle, switchtoMin, switchtoMax, state, isEmpty, and size.
Please guide me the pseudo code with above conditions

Answer 1

If u have any doubts please comment

Priority Queue is similar to queue where we insert an element
from the back and remove an element from front, but with a one
difference that the logical order of elements in the priority queue
depends on the priority of the elements. The element with highest
priority will be moved to the front of the queue and one with
lowest priority will move to the back of the queue.
Thus it is possible that when you enqueue an element at the back
in the queue,
it can move to front because of its highest priority.
We can use heaps to implement the priority queue.
It will take O(log N) time to insert and delete each element
in the priority queue.

Based on heap structure, priority queue also has two types
max- priority queue and min - priority queue.

MAX_PRIORITY QUEUE:-

Extract Maximum: In this operation, the maximum element will
be returned and the last element of heap will be placed at index 1
and max_heapify will be performed on node 1 as placing last element
on index 1 will violate the property of max-heap.

int extract_maximum (int Arr[ ])
{
    if(length == 0)
    {
   print “Can’t remove element as queue is empty”;
        return -1;
    }
    int max = Arr[1];
    Arr[1] = Arr[length];
    length = length -1;
    max_heapify(Arr, 1);
    return max;
}
Increase Value: In case increasing value of any node, may violate the property of max-heap, so we will swap the parent’s
value with the node’s value until we get a larger value on parent node.

void increase_value (int Arr[ ], int i, int val)
{
    if(val < Arr[ i ])
    {
        print ”New value is less than current value, can’t be inserted”;
        return;
    }
    Arr[ i ] = val;
    while( i > 1 and Arr[ i/2 ] < Arr[ i ])
    {
        swap|(Arr[ i/2 ], Arr[ i ]);
        i = i/2;
    }
}
Insert Value : //this function inserts the element to the queue

void insert_value (int Arr[ ], int val)
{
    length = length + 1;
    Arr[ length ] = -1; //assuming all the numbers greater than 0 are to be inserted in queue.
    increase_val (Arr, length, val);
}

void remove_value(){ // removes the value from the queue
   return Arr[--length]
}
int top(){ // return the top element from the queue
   return Arr[length-1]
}

boolean isEmpty(){ // return 0 if the queue is empty
   return length=0;
}
int Size(){ //return the length of the queue
   return length;
}

int switchTomin(int A[],int n){ // switches to the max_heap to the min_heap
   int i=(n-2)/2
   while(i>=0)
       min_heapify(A,i--,n);  
}
int switchTomax(int A[],int n){ //switches to the min_heap to the max_heap
   int i=(n-2)/2
   while(i>=0)
       max_heapify(A,i--,n);  
}
min_heapify(int A[],int i,int state){
   int left=left(i);
   int right=right(i);
   int smallest=i;
   if(left<size && A[left]<A[i]){
       smallest=left;
   }
   if(right<size && A[right]<A[smallest]){
       smallest=right;
   }
   if(smallest=i){
       swap(A[i],A[smallest]);
       Heapify(A,smallest,size);
   }
}
max_heapify(int A[],int i,int state){
   int left=left(i);
   int right=right(i);
   int largest=i;
   if(left>size && A[left]>A[i]){
       largest=left;
   }
   if(right>size && A[right]>A[largest]){
       largest=right;
   }
   if(largest!=i){
       swap(A[i],A[largest]);
       Heapify(A,largest,size);
   }
}
MIN_PRIORITY QUEUE:-

Extract Minimum: In this operation, the minimum element will
be returned and the last element of heap will be placed at index 1
and min_heapify will be performed on node 1 as placing last element
on index 1 will violate the property of min-heap.

int extract_manimum (int Arr[ ])
{
    if(length == 0)
    {
   print “Can’t remove element as queue is empty”;
        return -1;
    }
    int min = Arr[1];
    Arr[1] = Arr[length];
    length = length -1;
    min_heapify(Arr, 1);
    return min;
}
decrese Value: In case decresing value of any node, may violate the property of min-heap, so we will swap the parent’s value with the node’s value
until we get a smaller value on parent node.

void decrese_value (int Arr[ ], int i, int val)
{
    if(val > Arr[ i ])
    {
        print ”New value is greater than current value, can’t be inserted”
        return;
    }
    Arr[ i ] = val;
    while( i > 1 and Arr[ i/2 ] > Arr[ i ])
    {
        swap|(Arr[ i/2 ], Arr[ i ]);
        i = i/2;
    }
}
Insert Value :

void insert_value (int Arr[ ], int val)
{
    length = length + 1;
    Arr[ length ] = -1; //assuming all the numbers greater than 0 are to be inserted in queue.
    decrease_val (Arr, length, val);
}

void remove_value(){
   return Arr[--length]
}
int top(){
   return Arr[length-1]
}

boolean isEmpty(){
   return length=0;
}
int Size(){
   return length;
}

switchTomax(int A[],int n){
   int i=(n-2)/2
   while(i>=0)
       heapify(A,i--,n);  
}

int switchTomin(int A[],int n){
   int i=(n-2)/2
   while(i>=0)
       min_heapify(A,i--,n);  
}
int switchTomax(int A[],int n){
   int i=(n-2)/2
   while(i>=0)
       max_heapify(A,i--,n);  
}
min_heapify(int A[],int i,int state){
   int left=left(i);
   int right=right(i);
   int smallest=i;
   if(left<size && A[left]<A[i]){
       smallest=left;
   }
   if(right<size && A[right]<A[smallest]){
       smallest=right;
   }
   if(smallest=i){
       swap(A[i],A[smallest]);
       Heapify(A,smallest,size);
   }
}
max_heapify(int A[],int i,int state){
   int left=left(i);
   int right=right(i);
   int largest=i;
   if(left>size && A[left]>A[i]){
       largest=left;
   }
   if(right>size && A[right]>A[largest]){
       largest=right;
   }
   if(largest!=i){
       swap(A[i],A[largest]);
       Heapify(A,largest,size);
   }
}

here toggle function is not return because toggle means switching one state to other state that is already done in the SwitchTomin and SwitchTomax functins.