What is a priority queue?

A priority queue is a data structure in which every element has a priority, and on removal, the element chosen is not the one added first, but the highest-priority one.

#How it works

• Each element is stored as a pair: (value, priority).
• On insertion, the element is placed into the queue.
• On removal (dequeue), the element with the highest priority is extracted, not the one added earlier.

#Example

In a hospital, patients arrive in queue order, but the doctor sees those with a more severe condition first: they have a higher priority.

#Implementation

• The most common approach is through a heap, usually a min-heap or a max-heap.
  • Insertion (insert): O(log n),
  • Extracting the highest-priority element: O(log n),
  • Getting the maximum/minimum without removing it: O(1).

In this way, a priority queue is a queue where the order is determined not by arrival time, but by priority value.