Priority Queue

Idea Like You Are 10

In a normal queue, the first person in line goes first.

In a priority queue, a more important person may go first.

Example:

• emergency patient first
• regular patient later

So removal depends on priority, not just arrival time.

How It Works

Each item has:

• data
• priority

Example:

(A, 3), (B, 1), (C, 2)

If smaller number means higher priority, then B leaves first.

Common Operations

• insert item with priority
• delete highest-priority item
• peek highest-priority item

Simple Array-Based Method

Insert

If unsorted array is used:

insert(x, p):
    add (x, p) at the end

Time: O(1)

Delete Highest Priority

deletePriority():
    find highest-priority item
    remove it
    shift remaining items if needed

Time: O(n)

Peek Highest Priority

peekPriority():
    scan all items and return highest-priority one

Time: O(n)

Sorted Array Method

If the array is kept sorted by priority:

• insertion becomes O(n)
• deletion from front may become O(1)

Heap-Based Priority Queue

Using a heap:

• insertion: O(log n)
• deletion of highest priority: O(log n)
• peek: O(1)

This is the most common efficient implementation.

Complexity Summary

Applications

• CPU scheduling
• printer task handling
• network packet handling
• graph algorithms like Dijkstra and Prim