# Priority Queue using Arrays in C Programming

## Implementation of Priority Queue using Arrays in C

Priority Queue implementation using array is the one of the basic method to implement Queue. In Priority Queue data who has highest priority remove from the Queue first and second highest priority element after it and so on. In priority Queue each element has its own priority. If priority is same for two elements then data remove on the basis of first come first serve.

## Types of Priority Queue:

• Min Priority Queue: Minimum number of value gets the highest priority and lowest number of element gets the highest priority.
• Max Priority Queue: Maximum number value gets the highest priority and minimum number of value gets the minimum priority.

### Priority Queue Approaches

Priority Queue can be implemented in two ways:

• Using ordered Array: In ordered array enqueue operation takes O(n) time complexity because it enters elements in sorted order in queue. And deletion takes O(1) time complexity.
• Using unordered Array:In unordered array deletion takes O(n) time complexity because it search for the element in Queue for the deletion and enqueue takes o(1) time complexity.

## Implementing Priority Queue (Unordered)

Note : In below implementation we are taking example of Max priority queue, to implement min priority queue you can just change greater than sign to smaller than at the time of comparison and initialisation of maxPriority

• Enqueue – Insert the item at the end of the priority queue takes O(1) time
• Dequeue – Remove the item with the highest priority
• Peek – Return item with highest priority

### C Program (Priority Queue – Unordered using Array)

```//C program to Demonstrate Priority Queue#include<stdio.h>#include<limits.h>#define MAX 100

// denotes where the last item in priority queue is
// initialized to -1 since no item is in queue
int idx = -1;

// pqVal holds data for each index item
// pqPriority holds priority for each index item
int pqVal[MAX];
int pqPriority[MAX];

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

int isFull(){
return idx == MAX - 1;
}
// enqueue just adds item to the end of the priority queue | O(1)
void enqueue(int data, int priority)
{
if(!isFull()){

// Increase the index
idx++;

// Insert the element in priority queue
pqVal[idx] = data;
pqPriority[idx] = priority;
}
}

// returns item with highest priority
// NOTE: Max Priority Queue High priority number means higher priority | O(N)
int peek()
{
// Note : Max Priority, so assigned min value as initial value
int maxPriority = INT_MIN;
int indexPos = -1;

// Linear search for highest priority
for (int i = 0; i <= idx; i++) {         // If two items have same priority choose the one with         // higher data value         if (maxPriority == pqPriority[i] && indexPos > -1 && pqVal[indexPos] < pqVal[i])         {
maxPriority = pqPriority[i];
indexPos = i;
}

// note: using MAX Priority so higher priority number
// means higher priority
else if (maxPriority < pqPriority[i]) {
maxPriority = pqPriority[i];
indexPos = i;
}
}

// Return index of the element where
return indexPos;
}

// This removes the element with highest priority
// from the priority queue | O(N)
void dequeue()
{
if(!isEmpty())
{
// Get element with highest priority
int indexPos = peek();

// reduce size of priority queue by first
// shifting all elements one position left
// from index where the highest priority item was found
for (int i = indexPos; i < idx; i++) {
pqVal[i] = pqVal[i + 1];
pqPriority[i] = pqPriority[i + 1];
}

// reduce size of priority queue by 1
idx--;
}
}

void display(){
for (int i = 0; i <= idx; i++) {
printf("(%d, %d)\n",pqVal[i], pqPriority[i]);
}
}
// Driver Code
int main()
{
// To enqueue items as per priority
enqueue(5, 1);
enqueue(10, 3);
enqueue(15, 4);
enqueue(20, 5);
enqueue(500, 2);

printf("Before Dequeue : \n");
display();

// Dequeue the top element
dequeue(); // 20 dequeued
dequeue(); // 15 dequeued

printf("\nAfter Dequeue : \n");
display();

return 0;
}```

#### Output

```Before Dequeue :
(5, 1)
(10, 3)
(15, 4)
(20, 5)
(500, 2)

After Dequeue :
(5, 1)
(10, 3)
(500, 2)
```

## Implementing Priority Queue (Ordered Array)

Again we will take example of max priority queue below

• Dequeue – Dequeue item from the end O(1)
• Enqueue – Insert item in according to their priority, lowest priority at the start and highest priority at the end. Items are arranged in ascending sorted order of their priority value
• Peek – Return item with highest priority. Lsat item in the array itself will have highest priority

### C Program (Priority Queue – Ordered using Array)

Objective – Write a program in C to implement a priority queue using two-dimensional array, store elements and their respective priorities. display the elements according to priority from lower to higher.

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

// denotes where the last item in priority queue is
// initialized to -1 since no item is in queue
int idx = -1;

// pqVal holds data for each index item
// pqPriority holds priority for each index item
int pqVal[MAX];
int pqPriority[MAX];

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

int isFull(){
return idx == MAX - 1;
}
// Insert the element in maintaining items in sorted order
// of their priority
void enqueue(int data, int priority)
{
if(!isFull()){

// first item being entered
if(idx == -1){
idx++; // increase the index
pqVal[idx] = data;
pqPriority[idx] = priority;
return;
}
else{
// Increase the index
idx++;
// in reverse order
for(int i = idx-1; i >= 0;i--){
// shift all items rightwards with higher priority
// than the element we trying to insert
if(pqPriority[i] >= priority){
pqVal[i+1] = pqVal[i];
pqPriority[i+1] = pqPriority[i];
}
else{
// insert item just before where
// lower priority index was found
pqVal[i+1] = data;
pqPriority[i+1] = priority;
break;
}

}
}

}
}

// returns item with highest priority
// note highest priority in max priority queue is last item in array
int peek()
{
return idx;
}

// just reducing index would mean we have dequed
// the value would be sitll there but we can say that
// no more than a garbage value
void dequeue()
{
idx--;
}

void display(){
for (int i = 0; i <= idx; i++) {
printf("(%d, %d)\n",pqVal[i], pqPriority[i]);
}
}
// Driver Code
int main()
{
// To enqueue items as per priority
enqueue(25, 1);
enqueue(10, 10);
enqueue(15, 50);
enqueue(20, 100);
enqueue(30, 5);
enqueue(40, 7);

printf("Before Dequeue : \n");
display();

// // Dequeue the top element
dequeue(); // 20 dequeued
dequeue(); // 15 dequeued

printf("\nAfter Dequeue : \n");
display();

return 0;
}```

#### Output

```Before Dequeue :
(25, 1)
(30, 5)
(40, 7)
(10, 10)
(15, 50)
(20, 100)

After Dequeue :
(25, 1)
(30, 5)
(40, 7)
(10, 10)```

### 2 comments on “Priority Queue using Arrays in C Programming”

• ALPHA

hey nice resources add c++ also there is an typo in above text implementation in c ->insertion them instead of then 🙂

• HelpPrepInsta

Sorry for the silly mistake, we’ll fix it up 🙂