EDUCBA

EDUCBA

MENUMENU
  • Blog
  • Free Courses
  • All Courses
  • All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Priority Queue in Data Structure

Priority Queue in Data Structure

Updated March 6, 2023

Priority Queue in Data Structure

Introduction to Priority Queue

Priority queues are a special case of the queues where the elements are assigned the priorities according to requirement and further the operations are carried out depending on the priority of that particular element. In case, if more than one element inside the queue get the same priority then the serving or operations are carried out depending on the order in which they are placed inside the queue.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

In most cases, the priority queues are implemented in such a way that the value of that particular element itself acts as the priority parameter for it or is further manipulated to assign the priority. In this article, we will study the working of priority queue, how we can implement the priority queues using the C programming language, and also discuss the time complexity required to carry out the priority queue implementation.

Functions of priority Queue

The working of the priority queue is the same as that of normal queues where we perform operations like search (peek), insert, and delete some elements from it. The only difference is the selection of the element while deletion. Instead of the first element which is inserted, the highest priority element is selected for deletion. Consider the queue shown in the below figure –

Priority Queue in Data Structure 1

We can observe that from the one end the values are inserted in the queue pointed by enqueue but the dequeue operation will be carried out on the highest priority element. In the above figure, the element with the largest value has the highest priority, hence, 785 elements will be the first ones to be deleted from the priority queue.
The priority queue can be worked out by using Binary heap, binary search tree, and linked list. The time complexities for each of the operation in each of the case is as shown in the below table. It is upon your requirement that which operation is most frequently carried out on queue on the basis of which you can decide which data structure to be used for implementing priority queues-

Operations Binary Heap Linked List Binary Search Tree
Insert O (log n) O (n) O (log n)
Peek O (1) O (1) O (1)
Delete O (log n) O (1) O (log n)

Implementation of priority queue using the C programming language:

The following C program implements the priority queue by using the max-heap data structure and arrays.

// C program for implementing priority queue
#include <stdio.h>
int length = 0;
void swapTwoValues(int *item1, int *item2) {
int dummyItem = *item2;
*item2 = *item1;
*item1 = dummyItem;
}
// Prepare the heap for rerrangement of elements to carry out prepareHeap process
void prepareHeap(int array[], int length, int i) {
if (length == 1) {
printf("There is only one element in the Queue.");
} else {
// Detect the nodes which have the biggest value and its left and right child nodes.
int biggest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < length && array[l] > array[biggest])
biggest = l;
if (r < length && array[r] > array[biggest])
biggest = r;
// swapTwoValues and continue prepareHeaping if root is not biggest
if (biggest != i) {
swapTwoValues(&array[i], &array[biggest]);
prepareHeap(array, length, biggest);
}
}
}
// Function to addElement an element into the tree
void addElement(int array[], int newNumber) {
if (length == 0) {
array[0] = newNumber;
length += 1;
} else {
array[length] = newNumber;
length += 1;
for (int i = length / 2 - 1; i >= 0; i--) {
prepareHeap(array, length, i);
}
}
}
// Deletion of a particlar element from the array of max-heap tree
void rootDeletion(int array[], int number) {
int j;
for (j = 0; j < length; j++) {
if (number == array[j])
break;
}
swapTwoValues(&array[j], &array[length - 1]);
length -= 1;
for (int i = length / 2 - 1; i >= 0; i--) {
prepareHeap(array, length, i);
}
}
// Display the contents of array
void displayArray(int array[], int length) {
for (int i = 0; i < length; ++i)
printf("%d ", array[i]);
printf("\n");
}
// Controller of the program which calls different functions for manipulation
int main() {
int array[10];
addElement(array, 3);
addElement(array, 4);
addElement(array, 9);
addElement(array, 5);
addElement(array, 2);
printf("The contents of the max-heap array are : ");
displayArray(array, length);
rootDeletion(array, 4);
printf("The contents of the array after deleting one element from it: ");
displayArray(array, length);
}

The output of the above C program is as shown below displaying all the contents of the max -heap and also the updated contents after deleting one of the elements. The above program demonstrates the implementation of all three operations on the priority queue which are insertion, searching, and deletion. We can observe that while deleting the element from the priority queue it was the element with the highest priority that got deleted in this case the largest value element. While in m=normal queue the FIFO pattern which says that the first inserted element should be the first one to remove is not followed in case of priority queues.

Priority Queue in Data Structure 2

Time complexity

The time complexity of the priority queue, when implemented by using the above manner of using heap tree that is max-heap and the arrays, turns out to be O(n) where n is the number of elements. In the above example, the value of n is 5, hence, the complexity of time is O(5). The auxiliary space that is required is O(1).

Conclusion

The priority queue is just like a normal queue which performs enqueue a d dequeue operations to perform insertion or deletion of the element just the change is in the manner in which the value is selected for deletion. In the case of a normal queue, the FIFO pattern is followed which stands for the first in the first out format while deleting. In priority queues the elements are provided priorities according to the requirement like smallest element can be given highest priority or largest element can be given maximum priority. The element with the maximum priority is the first one to be chosen for deletion and then the next highest priority element and so on.

Recommended Articles

This is a guide to Priority Queue in Data Structure. Here we discuss the introduction, functions of priority Queue example with code implementation. You may also have a look at the following articles to learn more –

  1. Heap Data Structure
  2. Hashing in Data Structure
  3. Stack in Data Structure
  4. B+ Tree in Data Structure
All in One Excel VBA Bundle
500+ Hours of HD Videos
15 Learning Paths
120+ Courses
Verifiable Certificate of Completion
Lifetime Access
Financial Analyst Masters Training Program
2000+ Hours of HD Videos
43 Learning Paths
550+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Data Science Bundle
2000+ Hour of HD Videos
80 Learning Paths
400+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Software Development Bundle
5000+ Hours of HD Videos
149 Learning Paths
1050+ Courses
Verifiable Certificate of Completion
Lifetime Access
Primary Sidebar
All in One Data Science Bundle2000+ Hour of HD Videos | 80 Learning Paths | 400+ Courses | Verifiable Certificate of Completion | Lifetime Access
Financial Analyst Masters Training Program2000+ Hours of HD Videos | 43 Learning Paths | 550+ Courses | Verifiable Certificate of Completion | Lifetime Access
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more