Priority Queue – {Types, Operations, Implementation, Applications }

A Priority Queue is a specialized data structure where each element is associated with a priority, and the element with the highest (or lowest) priority is dequeued first. It does not follow the First-In-First-Out (FIFO) principle like a simple queue but is instead based on the priority of elements.

Types of Priority Queue

1. Max-Priority Queue: The element with the highest priority is dequeued first.  Following is the Max-Priority Queue Example 

• Elements: {(A, 2), (B, 5), (C, 1)}
• Sorted by priority: {(B, 5), (A, 2), (C, 1)}
• Dequeue order: B → A → C

2. Min-Priority Queue: The element with the lowest priority is dequeued first. Following is a Min-Priority Queue Example

• Elements: {(A, 2), (B, 5), (C, 1)}
• Sorted by priority: {(C, 1), (A, 2), (B, 5)}
• Dequeue order: C → A → B

Key Operations of Priority Queue

Each element has a priority associated with it. Elements are dequeued based on their priority, not their order of insertion. Here are two main operations of priority quueue

• Insertion (enqueue): Add an element with a given priority.
• Deletion (dequeue): Remove the element with the highest (or lowest) priority.

How Priority Queue Works (Implementation)

A priority queue can be implemented using various data structures, each with its own variants and characteristics. Here’s a breakdown:

1. Array-Based Implementation

• Unsorted Array:
  • Enqueue operation is O(1) (simply add to the end).
  • Dequeue operation is O(n) (find the highest priority element).
• Sorted Array:
  • Enqueue operation is O(n) (insert in sorted order).
  • Dequeue operation is O(1) (remove the first or last element).

2. Linked List-Based Implementation

• Unsorted Linked List:
  • Enqueue operation is O(1) (add at the head or tail).
  • Dequeue operation is O(n) (find the highest priority element).
• Sorted Linked List:
  • Enqueue operation is O(n) (insert at the correct position).
  • Dequeue operation is O(1) (remove the head or tail).

3. Heap-Based Implementation

• Binary Heap (Min-Heap or Max-Heap):
  • Enqueue (insert) and Dequeue (extract max/min) operations are both O(log⁡n).
  • Commonly used due to efficiency and simplicity.
• d-ary Heap:
  • A generalization of binary heap where each node has $d$ children.
  • Useful for specific applications (e.g., a 4-heap in Dijkstra’s algorithm for better performance).
• Fibonacci Heap:
  • Supports amortized O(1) insertion and O(log⁡n) for deletion.
  • Often used in advanced graph algorithms (e.g., Prim’s or Dijkstra’s).

4. Binary Search Tree (BST)

• Unbalanced BST:
  • Enqueue and Dequeue operations are O(h), where $h$ is the height of the tree (can degrade to O(n).
• Balanced BST (e.g., AVL Tree, Red-Black Tree):
  • Enqueue and Dequeue operations are O(log⁡n).
  • Priority queues can be implemented efficiently with balanced BSTs.

5. Specialized Data Structures

• Treap (Tree + Heap):
  • Combines BST and Heap properties.
  • Operations are O(log⁡n) on average.
• Pairing Heap:
  • A simpler alternative to Fibonacci Heap with similar efficiency.
  • Amortized $O(1)$ insertion and O(log⁡n) deletion.
• Binomial Heap:
  • Useful for merging two heaps efficiently.
  • Merging takes O(log⁡n).
• Skew Heap:
  • A variant of binary heap optimized for mergeable heaps.

Applications of Priority Queue

• Task Scheduling: CPU scheduling where high-priority tasks are executed first.
• Dijkstra’s Algorithm: Used to find the shortest path in a graph by prioritizing nodes with smaller weights.
• Data Compression: Huffman coding uses a priority queue to build a binary tree based on character frequencies.
• Event Simulation: Events are processed in the order of their scheduled time or priority.
• Operating Systems: Job scheduling in multi-tasking environments.