Priority Queue

data-structures algorithms

Definition

Priority Queue

A priority queue is an abstract data structure that operates similarly to a regular queue, but where each element has an associated priority. In a priority queue, an element with high priority is served before an element with low priority.

It provides two primary operations:

1. $\mathrm{insert}(v,p)$: Adds element $v$ with priority $p$.
2. $extract-max()$(or $extract-min()$): Removes and returns the element with the highest (or lowest) priority.

Implementation

The most common implementation of a priority queue is using a heap, as it provides an efficient balance between insertion and extraction time.

Implementation	$\mathrm{insert}$	$extract-max$
Unordered array	$O(1)$	$O(n)$
Ordered array	$O(n)$	$O(1)$
binary heap	$O(\log n)$	$O(\log n)$
Fibonacci heap	$O(1)$(amortised)	$O(\log n)$ (amortised)

Visual Representation

The following diagram illustrates the conceptual flow of a priority queue, where elements are reordered based on their priority values:

Use Cases

• Dijkstra’s Algorithm: Finding the shortest path in a graph.
• Huffman Coding: Data compression algorithms.
• Prim’s Algorithm: Finding the Minimum Spanning Tree (MST).
• Task Scheduling: Operating system kernel process scheduling.