What Is Priority Queue in Data Structure With Example?

What Is Priority Queue in Data Structure With Example?

A priority queue is a data structure that stores elements with associated priorities. The elements can be any data type, and the priority can be either a numerical value or any other comparable value. In a priority queue, the element with the highest (or lowest) priority is always at the front of the queue, allowing for efficient retrieval operations.

How Does a Priority Queue Work?

In a regular queue, elements are added to the back and removed from the front in a first-in-first-out (FIFO) manner. However, in a priority queue, elements are assigned priorities and are dequeued based on their priority rather than their arrival time.

A common real-life example of a priority queue is an emergency room where patients arrive with different levels of urgency. The patient with the most critical condition is given top priority and treated first, regardless of when they arrived.

Implementing Priority Queue

In programming languages like Python and Java, you can implement a priority queue using built-in libraries or by defining your own data structure.

Here’s an example of implementing a simple priority queue using Python:

<!-- Importing required library -->
import heapq

# Defining an empty list
priority_queue = []

# Adding elements to the priority queue
heapq.heappush(priority_queue, (3, 'Low Priority'))
heapq.heappush(priority_queue, (1, 'High Priority'))
heapq.heappush(priority_queue, (2, 'Medium Priority'))

# Removing elements from the priority queue
high_priority_element = heapq.heappop(priority_queue)
medium_priority_element = heapq.heappop(priority_queue)
low_priority_element = heapq.heappop(priority_queue)

In this example, we use the heapq library in Python, which provides functions for working with heaps. We define an empty list called priority_queue, and then we add elements to it using the heappush() function. Each element is a tuple containing the priority and the actual data.

To remove elements from the priority queue, we use the heappop() function, which returns the element with the highest priority.

Applications of Priority Queue

The priority queue data structure finds applications in various domains, including:

• Scheduling algorithms: Priority queues are used to schedule tasks based on their priorities. For example, in an operating system, processes with higher priority get more CPU time.
• Dijkstra’s algorithm: This popular graph traversal algorithm uses a priority queue to select the next vertex with the shortest distance during its execution.
• Huffman coding: This lossless data compression algorithm uses a priority queue to create an optimal prefix code for encoding characters based on their frequencies.

Conclusion

A priority queue is a versatile data structure that allows efficient retrieval of elements based on their priorities. It can be implemented using built-in libraries or by defining your own data structure. Understanding and utilizing the priority queue can greatly enhance program efficiency and solve various real-world problems effectively.

Now that you have a clear understanding of what a priority queue is and how it works, you can explore further applications and implement it in your own projects!