Priority Queue Insertion and Deletion in C

March 20, 2025

C Program to Insert or Delete Element from Priority Queue

On this page we will discuss about Priority Queue Insertion and Deletion in C 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

Priority Queue Insertion And Deletion

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)

Queues In Data Structures

Circular queue in C

Priority Queue in C

Priority Queue Implementation using Array

Tree Traversals: Inorder Postorder Preorder

C Program for Inserting and Deleting elements in Priority Queue

Run 
// 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;
}

Output

Before: 
(10, 1)
(20, 3)
(30, 4)
(40, 5)
(1000, 2)

After: 
(20, 3)
(30, 4)
(40, 5)