Priority Queue using Array in C

priority queue using array in C

Priority Queue

Priority queues are abstract data structures where each element in the queue has a priority value. For example, in any airline, baggage under the “First-Class” or “Business” arrives before other baggage.
A priority Queue is a type of queue that follows the given below properties:

  • An item with higher priority will be dequeued before the item with lower priority.
  • If two elements present in the priority queue are having the same priority, then they will be served according to the order in which they are present in the queue.

The priority queue is widely used in many applications like job scheduling algorithms, CPU and Disk scheduling, and managing various resources shared between different processes, etc.

How is the Priority Value assigned in the Priority Queue?

In c, priority value will be given at the time of insertion of element. And on the basis of that priority value elements will be chosen for performing the operations. Elements with higher priority value will be served first for the operations as compared to elements with lower priority value.

The main difference between a queue and a priority queue:

In the queue, the element inserted first will be dequeued first. But in the case of a priority queue, the element which is having highest priority will be dequeued first.
When an element is popped out of the priority queue, the result will be in the sorted order, it can be either increasing or decreasing. While in queue elements are popped out in the order of FIFO (First in First out).

Code Implementation


#include<stdio.h>
#include<limits.h>
#define MAX 100

int idx = -1;

int pqVal[MAX];
int pqPriority[MAX];



int isEmpty(){
    return idx == -1;
}

int isFull(){
    return idx == MAX - 1;
}

void enqueue(int data, int priority)
{
    if(!isFull()){
        
        idx++;
 
        pqVal[idx] = data;
        pqPriority[idx] = priority;
    }
}

int peek()
{
    int maxPriority = INT_MIN;
    int indexPos = -1;
 
    for (int i = 0; i <= idx; i++) { 
        if (maxPriority == pqPriority[i] && indexPos > -1 && pqVal[indexPos] < pqVal[i]) 
        {
            maxPriority = pqPriority[i];
            indexPos = i;
        }
        
        else if (maxPriority < pqPriority[i]) {
            maxPriority = pqPriority[i];
            indexPos = i;
        }
    }
    
    return indexPos;
}

void dequeue()
{
    if(!isEmpty())
    {
        int indexPos = peek();

        for (int i = indexPos; i < idx; i++) {
            pqVal[i] = pqVal[i + 1];
            pqPriority[i] = pqPriority[i + 1];
        }
 
        idx--;
    }
}

void display(){
    for (int i = 0; i <= idx; i++) {
        printf("(%d, %d)\n",pqVal[i], pqPriority[i]);
    } 
}

int main()
{
    enqueue(5, 1);
    enqueue(10, 3);
    enqueue(15, 4);
    enqueue(20, 5);
    enqueue(25, 2);
    
    printf("Priority Queue Before Dequeue : \n");
    display();
 
    dequeue(); 
    dequeue();
    
    printf("\nPriority Queue After Dequeue : \n");
    display();

    return 0;
}

This article tried to discuss the implementation of Priority Queue using Array in C with the help of examples. Hope this blog helps you understand the concept. To learn more feel free to check Foundation Courses at Prepbytes

Leave a Reply

Your email address will not be published. Required fields are marked *