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.

Priority Queue

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”