Priority queues are essential data structures that manage elements based on their priorities. Unlike regular queues that follow FIFO, priority queues serve higher priority elements first, making them crucial for various applications like task scheduling and event simulations.

Understanding priority queues is vital for efficient algorithm design. They offer a balance between insertion and extraction time complexities, typically implemented using binary heaps. This makes them ideal for scenarios where processing order matters more than arrival order.

Priority Queue Fundamentals

Priority queue ADT and operations

• Models collection of elements with priorities attached
• Higher priority elements served before lower priority elements
• Insert(element, priority) adds element with associated priority to queue
• ExtractMax() or ExtractMin() removes and returns element with highest or lowest priority (max or min queue)
• Peek() returns element with highest or lowest priority without removing
• IsEmpty() checks if queue is empty
• Size() returns number of elements in queue

Priority vs regular queues

• Regular queue follows First-In-First-Out (FIFO) principle
  • Elements processed in order added to queue
  • No concept of priority
• Priority queue processes elements based on priority
  • Higher priority elements served before lower priority elements regardless of insertion order
  • Same priority elements processed according to order in queue

Real-world applications of priority queues

• Task scheduling in operating systems
  • Higher priority tasks executed before lower priority tasks
• Event-driven simulations
  • Events with earlier timestamps processed first
• Dijkstra's shortest path algorithm
  • Efficiently selects vertex with minimum distance at each step
• Huffman coding for data compression
  • Characters with higher frequencies assigned shorter bit representations
• Minimum spanning tree algorithms (Prim's algorithm)
  • Selects vertex with minimum edge weight at each step

Time complexity of priority queues

• Priority queue (binary heap implementation)
  1. Insert: $O(\log n)$
  2. ExtractMax/ExtractMin: $O(\log n)$
  3. Peek: $O(1)$
• Regular queue (array or linked list implementation)
  1. Enqueue: $O(1)$
  2. Dequeue: $O(1)$
  3. Front: $O(1)$
• Sorted array
  1. Insert: $O(n)$ requires shifting elements
  2. ExtractMax/ExtractMin: $O(1)$ element at end or beginning
  3. Peek: $O(1)$
• Unsorted array
  1. Insert: $O(1)$ append at end
  2. ExtractMax/ExtractMin: $O(n)$ requires linear search
  3. Peek: $O(n)$ requires linear search

Priority queues balance insertion and extraction time complexities, efficient for processing elements based on priorities