Priority Queue Insertion and Deletion in C

C Program to Insert or Delete Element from Priority Queue

On this page we will understand what priority queue is and how its implemented using arrays and write a program to insert and delete elements in the priority queue
Priority Queue Insertion and Deletion in C

Introduction

A priority is basically an extension of the general queue. A major difference is that dequeuing happens based on the priority of each item in the queue.

We have two types of priority queue –

  • Max Priority Queue – A larger priority value means higher priority
  • Min Priority Queue – A smaller priority value means lower priority

By default, if nothing is mentioned it means that the Priority queue is a min priority queue.

A Priority Queue can be implemented using –

  • Arrays
  • Linked List
  • Heaps

You can check these pages here for implementation using Linked List and arrays

We will be discussing the array approach here.

Operations

  • enqueue(): To insert a new item at the end of the queue.
  • dequeue(): To remove the element with the highest priority from the queue.
  • peek()/top(): To get the highest priority element in the queue without dequeuing the item.

Time Complexity 

  • enqueue(): O(1)
  • dequeue(): O(n)
  • peek()/top(): O(n)

C Program for Inserting and Deleting elements in Priority Queue

// Write a program to insert and delete elements in the 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; // pqData holds data for each index item // pqPriority holds priority for each index item int pqData[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 pqData[idx] = data; pqPriority[idx] = priority; } } // returns item with highest priority // NOTE: Low priority number means higher priority | O(N) int peek() { int maxPriority = INT_MAX; 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 && pqData[indexPos] < pqData[i])
{
maxPriority = pqPriority[i];
indexPos = i;
}
// note low priority number means higher priority
// ex: Two processes P1 - 1 priority and P2 - 5 priority
// P1 will get executed first, thus comes out of ready queue first
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++) { pqData[i] = pqData[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",pqData[i], pqPriority[i]); } } // Driver Code int main() { // To enqueue items as per priority enqueue(10, 1); enqueue(20, 3); enqueue(30, 4); enqueue(40, 5); enqueue(1000, 2); printf("Before: \n"); display(); // Dequeue the top element dequeue(); // 10 dequeued dequeue(); // 1000 dequeued printf("\nAfter: \n"); display(); return 0; }