9/7/2023

Data Structure
Name : Ritik Kumar Ram Sah
Class : Sy Bsc IT Sem 3
Division : A
Roll No : 45
Seat No : 22078
Subject : Data Structure
Topic : Priority Queue

Structure
• A priority queue is a data structure that stores a collection of elements and provides
constant time access to the element with the highest priority.
• In C, a priority queue can be implemented using a structure that contains the element
and its priority.
• In a priority queue, each element has a priority value associated with it. When you add an element
to the queue, it is inserted in a position based on its priority value. For example, if you add an
element with a high priority value to a priority queue, it may be inserted near the front of the
queue, while an element with a low priority value may be inserted near the back.

1
 9/7/2023

Memory Representation of Priority Queue

Types of Priority Queue:

1) Ascending Order Priority Queue

As the name suggests, in ascending order priority queue, the element with a lower priority value is
given a higher priority in the priority list. For example, if we have the following elements in a
priority queue arranged in ascending order like 4,6,8,9,10. Here, 4 is the smallest number, therefore,
it will get the highest priority in a priority queue and so when we dequeue from this type of priority
queue, 4 will remove from the queue and dequeue returns 4.

2) Descending order Priority Queue

The root node is the maximum element in a max heap, as you may know. It will also remove the
element with the highest priority first. As a result, the root node is removed from the queue. This
deletion leaves an empty space, which will be filled with fresh insertions in the future. The heap
invariant is then maintained by comparing the newly inserted element to all other entries in the
queue.

2
 9/7/2023

Algorithm
• Algorithm for implementing Priority Queue using Binary Heap

Step1: Create a function heapify() to heapify the elements in the Binary Tree if any changes are made.
Step2: Find the largest among root, left child, and right child, then recursively call the same function until the root element
matches the largest element.
Step3: Create a function insert() to insert an element into the tree, which takes an array and the number which is to be inserted
as input.
Step 4: If the size of the array is zero, then this number will be the root, else append the number and call the heapify function
recursively to heapify the elements.
Step5: Create a function deleteNode() that deletes the selected element from the tree
Step 6: Delete the element and again heapify the elements recursively.
Step 7: Insert elements into an empty array using the insert() function then try deleting an element from the tree.

3
 9/7/2023

Pictorial Representation
• Here's a simple pictorial representation of a min-heap priority queue:

2
/ \
5 8
/ \ / \
9 11 12 14

• In this pictorial representation:

• The number 2 is at the root, representing the highest priority element.
• The parent nodes (2, 5, 8) have smaller values than their child nodes.
• The elements are organized in a way that maintains the min-heap property.
• You can imagine this as a binary tree, where each level of the tree represents a
different priority level. The root has the highest priority, and as you move down
the tree, the priority decreases.
• When you insert an element with a priority, it is placed at the bottom of the tree,
and then a "heapify up" operation is performed to move it to its correct position
to maintain the min-heap property. Similarly, when you extract an element, the
root element is removed, and the last element in the heap is moved to the root
position. Then, a "heapify down" operation is performed to restore the min-heap
property.
• This is a simplified representation, and in practice, priority queues can be
implemented using arrays, linked lists, or other data structures, with various
optimizations for different use cases. The key idea is to ensure that elements are
ordered by their priorities, with efficient insertion and extraction operations.
•

4
 9/7/2023

Operation of a Priority Queue

A typical priority queue supports the following operations:
1) Insertion in a Priority Queue
When a new element is inserted in a priority queue, it moves to the empty slot from top to bottom
and left to right. However, if the element is not in the correct place then it will be compared with
the parent node. If the element is not in the correct order, the elements are swapped. The
swapping process continues until all the elements are placed in the correct position.
2) Deletion in a Priority Queue
As you know that in a max heap, the maximum element is the root node. And it will remove the
element which has maximum priority first. Thus, you remove the root node from the queue. This
removal creates an empty slot, which will be further filled with new insertion. Then, it compares
the newly inserted element with all the elements inside the queue to maintain the heap invariant.
3) Peek in a Priority Queue
This operation helps to return the maximum element from Max Heap or the minimum element from
Min Heap without deleting the node from the priority queue.

Implementation of Priority Queue

Priority queue can be implemented using the following data structures:
• Arrays
• Linked list
• Heap data structure
• Binary search tree

5
 9/7/2023

Let’s discuss all these in detail.

• 1) Implement Priority Queue Using Array:
A simple implementation is to use an array of the following structure.
struct item {
int item;
int priority;
}

enqueue(): This function is used to insert new data into the queue.
dequeue(): This function removes the element with the highest priority from the queue.
peek()/top(): This function is used to get the highest priority element in the queue without
removing it from the queue.

• 2) Implement Priority Queue Using Linked List:

In a LinkedList implementation, the entries are sorted in descending order based on their priority.
The highest priority element is always added to the front of the priority queue, which is formed
using linked lists. The functions like push(), pop(), and peek() are used to implement a priority
queue using a linked list and are explained as follows:
push(): This function is used to insert new data into the queue.
pop(): This function removes the element with the highest priority from the queue.
peek() / top(): This function is used to get the highest priority element in the queue without
removing it from the queue.

6
 9/7/2023

• 3) Implement Priority Queue Using Heaps:

Binary Heap is generally preferred for priority queue implementation because heaps provide better
performance compared to arrays or LinkedList. Considering the properties of a heap, The entry with
the largest key is on the top and can be removed immediately. It will, however, take time O(log n) to
restore the heap property for the remaining keys. However if another entry is to be inserted
immediately, then some of this time may be combined with the O(log n) time needed to insert the
new entry. Thus the representation of a priority queue as a heap proves advantageous for large n,
since it is represented efficiently in contiguous storage and is guaranteed to require only logarithmic
time for both insertions and deletions. Operations on Binary Heap are as follows:
insert(p): Inserts a new element with priority p.
extractMax(): Extracts an element with maximum priority.
remove(i): Removes an element pointed by an iterator i.
getMax(): Returns an element with maximum priority.
changePriority(i, p): Changes the priority of an element pointed by i to p.

• 4) Implement Priority Queue Using Binary Search Tree:

• A Self-Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc. can also be used to
implement a priority queue. Operations like peek(), insert() and delete() can be performed using
BST.

7
 9/7/2023

C Program (Implementation)
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a task

typedef struct {
int priority;
char description[100];
} Task;

// Function to compare two tasks by priority

int compareTasks(const void *a, const void *b) {
return ((Task *)a)->priority - ((Task *)b)->priority;
}

int main() {
int choice;
Task taskQueue[100]; // Array to store tasks (adjust the size as needed)
int taskCount = 0;

while (1) {
printf("\nPriority Queue Menu:\n");
printf("1. Add Task\n");
printf("2. Execute Task\n");
printf("3. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1: // Add Task
if (taskCount < sizeof(taskQueue) / sizeof(taskQueue[0])) {
printf("Enter task description: ");
scanf("%s", taskQueue[taskCount].description);
printf("Enter task priority: ");
scanf("%d", &taskQueue[taskCount].priority);

// Add the task to the priority queue

taskCount++;
qsort(taskQueue, taskCount, sizeof(Task), compareTasks);
printf("Task added successfully.\n");
} else {
printf("Task queue is full. Cannot add more tasks.\n");
}
break;

8
 9/7/2023

case 2: // Execute Task

if (taskCount > 0) {

printf("Executing task: %s\n", taskQueue[0].description);

// Remove the highest-priority task (the first task in the queue)

for (int i = 0; i < taskCount - 1; i++) {

taskQueue[i] = taskQueue[i + 1];

taskCount--;

} else {

printf("No tasks to execute.\n");

break;

case 3: // Exit

printf("Exiting the program.\n");

exit(0);

default:

printf("Invalid choice. Please try again.\n");

return 0;

9
 9/7/2023

References:
ChatGPT
Website : geeksforgeeks

10