Course contentsShow
← Computer Science
Lesson 390 of 2,8729. Stacks and QueuesFree lesson

Priority Queue Array Implementation

Implementing priority queues using sorted or unsorted arrays and analyzing their tradeoffs.

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.