👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Linear Data Structures
Study mode

Priority queues

Study Practice Revise 🔒 Test

Introduction to Priority Queues

In the study of data structures, linear data structures such as arrays, linked lists, stacks, and queues organize data elements in a sequential manner. For example, a queue follows the First-In-First-Out (FIFO) principle, where elements are processed in the exact order they arrive.

However, many real-world scenarios require processing elements not just by arrival time but by their importance or priority. This is where priority queues come into play. A priority queue is a special type of queue where each element is associated with a priority, and elements with higher priority are processed before those with lower priority, regardless of their arrival order.

Understanding priority queues is essential for solving problems that involve scheduling, resource management, and optimization, especially in competitive exams and real-world applications.

Definition and Characteristics of Priority Queues

A priority queue is an abstract data type similar to a regular queue but with an added feature: each element has a priority. When removing (dequeueing) an element, the one with the highest priority is always chosen first.

Unlike a regular queue where the order is strictly FIFO, a priority queue orders elements based on their priority values.

Key Concept: In a priority queue, the element with the highest priority is dequeued first. If two elements have the same priority, the order of their arrival can determine which is dequeued first (depending on implementation).

For example, consider a hospital emergency room:

  • Patients arrive and wait to be treated.
  • Instead of treating patients in the order they arrive, doctors treat patients based on the severity of their condition (priority).
  • A patient with a critical injury is treated before a patient with a minor injury, even if the latter arrived earlier.
A (2) B (5) C (8) D (3) E (7) C (8) E (7) B (5) D (3) A (2)

In the diagram above, elements labeled A to E have different priorities (numbers in parentheses). When dequeuing, the element with the highest priority (C with 8) is removed first, followed by E (7), then B (5), and so on, regardless of their original order in the queue.

Implementation Techniques

Priority queues can be implemented using several data structures, each with its own advantages and disadvantages. The most common methods are:

  • Array-based Implementation
  • Linked List Implementation
  • Heap-based Implementation
Implementation Insertion Complexity Deletion (Extract Max/Min) Complexity Ease of Implementation Notes
Unsorted Array O(1) O(n) (search for max/min) Easy Fast insertion, slow deletion
Sorted Array O(n) (insert at correct position) O(1) Moderate Fast deletion, slow insertion
Sorted Linked List O(n) (traverse to insert) O(1) Moderate Dynamic size, no shifting needed
Heap (Binary Heap) O(log n) O(log n) Moderate to Complex Balanced performance, widely used

The heap-based implementation is the most efficient for large datasets, offering logarithmic time for both insertion and deletion. Arrays and linked lists can be simpler but may suffer from slower operations depending on whether they are sorted or unsorted.

Operations on Priority Queues

The main operations supported by priority queues are:

  • Insertion: Add a new element with a given priority.
  • Deletion (Extract Max/Min): Remove and return the element with the highest (or lowest) priority.
  • Peek: View the element with the highest priority without removing it.

Below is a flowchart illustrating the insertion and deletion process in a heap-based priority queue:

graph TD    A[Start] --> B{Operation?}    B -->|Insert| C[Add element at end]    C --> D[Heapify-up to maintain heap property]    D --> E[Insertion complete]    B -->|Delete| F[Remove root element]    F --> G[Replace root with last element]    G --> H[Heapify-down to maintain heap property]    H --> I[Deletion complete]

In a max-heap (a common type of heap), the root node always contains the element with the highest priority. When inserting, the new element is added at the end and then "heapified up" to restore the max-heap property. When deleting, the root is removed, replaced by the last element, and then "heapified down".

Worked Examples

Example 1: Inserting Elements into a Max-Heap Priority Queue Medium
Insert the following elements with priorities into an empty max-heap priority queue in the order: 15, 10, 30, 40, 20. Show the heap after each insertion.

Step 1: Insert 15.

Heap: [15]

Step 2: Insert 10.

Heap before heapify-up: [15, 10]

Since 10 < 15, no change.

Heap after heapify-up: [15, 10]

Step 3: Insert 30.

Heap before heapify-up: [15, 10, 30]

Compare 30 with parent 15; 30 > 15, so swap.

Heap after heapify-up: [30, 10, 15]

Step 4: Insert 40.

Heap before heapify-up: [30, 10, 15, 40]

Compare 40 with parent 10; 40 > 10, swap.

Heap now: [30, 40, 15, 10]

Compare 40 with new parent 30; 40 > 30, swap.

Heap after heapify-up: [40, 30, 15, 10]

Step 5: Insert 20.

Heap before heapify-up: [40, 30, 15, 10, 20]

Compare 20 with parent 30; 20 < 30, no swap.

Heap after heapify-up: [40, 30, 15, 10, 20]

Answer: Final max-heap array representation is [40, 30, 15, 10, 20].

Example 2: Extracting the Highest Priority Element Medium
Given the max-heap [50, 30, 40, 10, 20], remove the highest priority element and show the heap after reheapification.

Step 1: Remove the root element 50.

Step 2: Replace root with last element 20.

Heap now: [20, 30, 40, 10]

Step 3: Heapify-down from root:

  • Compare 20 with children 30 and 40.
  • 40 is largest child; swap 20 and 40.

Heap now: [40, 30, 20, 10]

Step 4: Continue heapify-down at index of 20:

  • Children of 20 are 10 (only one child).
  • 20 > 10, no swap needed.

Answer: Heap after extraction: [40, 30, 20, 10]

Example 3: Priority Queue Using Linked List Easy
Implement a priority queue using a sorted linked list. Insert elements with priorities 25, 15, 30, 10, and then delete the highest priority element.

Step 1: Insert 25.

List: 25

Step 2: Insert 15.

Insert 15 in sorted order (descending): 25 -> 15

Step 3: Insert 30.

30 > 25, so insert at head: 30 -> 25 -> 15

Step 4: Insert 10.

Insert at end: 30 -> 25 -> 15 -> 10

Step 5: Delete highest priority element (head): remove 30.

List after deletion: 25 -> 15 -> 10

Answer: Final linked list after operations is 25 -> 15 -> 10.

Example 4: CPU Scheduling Simulation Using Priority Queue Hard
Simulate a CPU scheduling scenario where processes arrive with priorities: P1(3), P2(1), P3(4), P4(2). Use a priority queue to decide the order of execution.

Step 1: Insert processes into a max-priority queue based on priority values.

Insert P1(3): Queue: [P1]

Insert P2(1): Queue: [P1, P2]

Insert P3(4): Queue after heapify: [P3, P2, P1]

Insert P4(2): Queue after heapify: [P3, P4, P1, P2]

Step 2: Process execution order is determined by extracting max priority:

  1. Extract P3(4)
  2. Extract P1(3)
  3. Extract P4(2)
  4. Extract P2(1)

Answer: The CPU executes processes in order: P3 -> P1 -> P4 -> P2.

Example 5: Dijkstra's Algorithm Step Using Priority Queue Hard
In Dijkstra's algorithm, given the current distances to vertices: A(0), B(4), C(2), D(∞), use a min-priority queue to select the next vertex to process.

Step 1: Insert vertices with their current distances into a min-priority queue.

Queue: [(A,0), (B,4), (C,2), (D,∞)]

Step 2: Extract the vertex with minimum distance.

Extracted: A(0)

Step 3: Update distances of neighbors and reinsert or update their priorities in the queue as needed.

Answer: The priority queue efficiently selects the next vertex with the smallest tentative distance, which is crucial for Dijkstra's algorithm's performance.

Tips & Tricks

Tip: Use a max-heap for extracting the highest priority and a min-heap for the lowest priority.

When to use: When you need efficient access to either maximum or minimum priority elements.

Tip: Memorize the heap index formulas: parent(i) = \(\left\lfloor \frac{i-1}{2} \right\rfloor\), left(i) = \(2i + 1\), right(i) = \(2i + 2\).

When to use: During heap implementation or debugging.

Tip: For small datasets, a sorted linked list can be simpler and efficient enough.

When to use: When ease of implementation is more important than performance.

Tip: Practice visualizing heap insertions and deletions step-by-step to avoid confusion.

When to use: Preparing for competitive exams or coding interviews.

Tip: Use priority queues to optimize greedy algorithms like Dijkstra's or Huffman coding.

When to use: When solving graph or encoding problems requiring efficient priority management.

Common Mistakes to Avoid

❌ Confusing priority queue with a regular queue and expecting FIFO behavior.
✓ Remember that priority queues dequeue elements based on priority, not arrival order.
Why: Students often rely on queue intuition and overlook the priority aspect.
❌ Incorrectly calculating parent or child indices in heap implementations.
✓ Use the formulas: parent(i) = \(\left\lfloor \frac{i-1}{2} \right\rfloor\), left(i) = \(2i + 1\), right(i) = \(2i + 2\).
Why: Indexing errors lead to incorrect heap structure and bugs.
❌ Not maintaining heap property after insertion or deletion.
✓ Always perform heapify-up after insertion and heapify-down after deletion.
Why: Skipping heapify leads to invalid priority queue behavior.
❌ Using unsorted linked list for priority queue leading to inefficient operations.
✓ Use a sorted linked list or heap to ensure efficient insertion and deletion.
Why: Unsorted lists require linear search, increasing time complexity.
❌ Mixing up max-heap and min-heap when the problem requires a specific priority order.
✓ Clarify problem requirements and choose appropriate heap type accordingly.
Why: Wrong heap type leads to incorrect priority extraction.

Formula Bank

Heap Parent Index
\[ parent(i) = \left\lfloor \frac{i-1}{2} \right\rfloor \]
where: \(i\) = current node index
Heap Left Child Index
\[ left(i) = 2i + 1 \]
where: \(i\) = current node index
Heap Right Child Index
\[ right(i) = 2i + 2 \]
where: \(i\) = current node index
Time Complexity of Operations
\[ \text{Insertion: } O(\log n), \quad \text{Deletion: } O(\log n), \quad \text{Peek: } O(1) \]
where: \(n\) = number of elements in the priority queue
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Priority queues · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.