Priority Queue Array Implementation
You'll learn how to build a priority queue using arrays and understand the performance tradeoffs of different approaches.
The Core Idea
A priority queue can be implemented with arrays in two main ways: using an unsorted array or a sorted array. Each approach makes different tradeoffs between insertion speed and retrieval speed.
Think of it like organizing a to-do list. You could either:
- Write tasks down as they come (unsorted), then search through everything to find the most important one
- Keep tasks in priority order always (sorted), so the most important is always on top
Unsorted Array Approach
With an unsorted array, you insert new elements at the end—fast and simple, just like adding to a regular queue. When you need to remove the highest-priority item, you scan through the entire array to find it.
- Insert: O(1) — just append to the end
- Remove highest priority: O(n) — must search entire array
- Best for: Frequent insertions, rare removals
Sorted Array Approach
With a sorted array, you maintain elements in priority order at all times. Insertion requires finding the correct position and potentially shifting elements. Removal is trivial—just take from the front (or back, depending on how you sort).
- Insert: O(n) — must find position and shift elements
- Remove highest priority: O(1) — always at one end
- Best for: Frequent removals, rare insertions
Which to Choose?
Neither is perfect—both have an O(n) operation. The choice depends on your usage pattern. Later, you'll learn about heap-based implementations that improve both operations to O(log n).
Key Takeaway: Priority queues can use unsorted arrays (fast insert, slow remove) or sorted arrays (slow insert, fast remove)—each trades off insertion versus removal performance.