Introduction to Priority Queue





A priority queue is a type of queue that arranges elements based on their

priority values.
 Each element has a priority associated. When we add an item, it is
inserted in a position based on its priority.
 Elements with higher priority are typically retrieved or removed before
elements with lower priority.
 Binary heap is the most common method to implement a priority queue.
In binary heaps, we have easy access to the min (in min heap) or max
(in max heap) and binary heap being a complete binary tree are easily
implemented using arrays. Since we use arrays, we have cache
friendliness advantage also.
 Priority Queue is used in algorithms such as Dijkstra's algorithm, Prim's
algorithm, and Huffman Coding.
For example, in the below priority queue, an element with a maximum
ASCII value will have the highest priority. The elements with higher priority
are served first.
Types of Priority Queue

Types of Priority Queue

 Ascending Order Priority Queue : In this queue, elements with lower
values have higher priority. For example, with elements 4, 6, 8, 9, and
10, 4 will be dequeued first since it has the smallest value, and the
dequeue operation will return 4.
 Descending order Priority Queue : Elements with higher values have
higher priority. The root of the heap is the highest element, and it is
 dequeued first. The queue adjusts by maintaining the heap property
after each insertion or deletion.
The following is an example of Descending order Priority Queue.

How Priority is Determined in a Priority Queue?

In a priority queue, generally, the value of an element is considered for
assigning the priority. For example, the element with the highest value is
assigned the highest priority and the element with the lowest value is
assigned the lowest priority. The reverse case can also be used i.e., the
element with the lowest value can be assigned the highest priority. Also,
the priority can be assigned according to our needs.
Operations on a Priority Queue
A typical priority queue supports the following operations:
1) Insertion : If the newly inserted item is of the highest priority, then it is
inserted at the top. Otherwise, it is inserted in such a way that it is
accessible after all higher priority items are accessed.
2) Deletion : We typically remove the highest priority item which is typically
available at the top. Once we remove this item, we need not move next
priority item at the top.
3) Peek : This operation only returns the highest priority item (which is
typically available at the top) and does not make any change to the priority
queue.
Difference between Priority Queue and Normal
Queue
There is no priority attached to elements in a queue, the rule of first-in-first-
out(FIFO) is implemented whereas, in a priority queue, the elements have
a priority. The elements with higher priority are served first.

Implementation of Priority Queue

Priority queue can be implemented using the following data structures:
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.
Arrays enqueue() dequeue() peek()

Time Complexity O(1) O(n) O(n)

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.
Linked List push() pop() peek()

Time Complexity O(n) O(1) O(1)

Note: We can also use Linked List, time complexity of all operations with
linked list remains same as array. The advantage with linked list
is deleteHighestPriority() can be more efficient as we don't have to move
items.

3) Implement Priority Queue Using Heap:

A Binary Heap is ideal for priority queue implementation as it offers better
performance than arrays or linked lists. The largest key is at the top and
can be removed in O(log n) time, with the heap property restored efficiently.
If a new entry is inserted immediately, its O(log n) insertion time may
overlap with restoration. Since heaps use contiguous storage, they
efficiently handle large datasets while ensuring logarithmic time for
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.
Binary Heap insert() remove() peek()

Time Complexity O(log n) O(log n) O(1)

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.
Binary Search Tree peek() insert() delete()

Time Complexity O(1) O(log n) O(log n)

Problems Based on Priority Queue or Heap

The following list of top coding problems on Heap covers a range of
difficulty levels, from easy to hard, to help candidates prepare
for interviews.

Applications of Priority Queue

 CPU Scheduling
 Graph algorithms like Dijkstra's shortest path algorithm, Prim's Minimum
Spanning Tree, etc.
 All queue applications where priority is involved.
 Data compression in Huffman code
 Event-driven simulation such as customers waiting in a queue.
 Finding Kth largest/smallest element.