CITS2200 - Lecture 17

← Back to Home

CITS2200 - Lecture 16
Priority Queues - Slides

Priority Queues

• A priority queue stores items as (key, value) pairs
• Smallest key (integer) = highest priority
• Items are removed in key order, not insertion order

Core operations:

Method	What it does	Notes
add(k, x)	Insert item with key k, value x	Always allowed
remove_min()	Remove + return smallest-key item	Error if empty
min()	Peek at smallest-key item (no removal)	Error if empty
len(P)	Number of items	—
is_empty()	True if no items	—

Keys must satisfy total order relation: reflexive, antisymmetric, transitive

---

Sequence Based Priority Queue

Two Sequence-Based Approaches:

1. Unsorted List
   • add -> $O(1)$
   • remove_min -> $O(n)$
   • min -> $O(n)$
2. Sorted List
   • add -> $O(n)$
   • remove_min -> $O(1)$
   • min -> $O(1)$

There is a trade-off depending on which approach is used. It takes more time searching for the min in an unsorted list, but maintaining a sorted list is harder as additions must preserve order

The ideal implementation is a heap:

• $O(\log n)$ for both additions and searches

---

Priority Queue Sorting

• Any priority queue can be used to sort a sequence:
  1. Insert all elements
  2. Extract all elements with remove_min()
     • Items come out in sorted order

Selection-Sort -> $O(n^2)$

• Phase 1: $O(n)$ $-$ append each element
• Phase 2: $O(n^2)$ $-$ remove_min scans whole unsorted PQ

Insertion-Sort -> $O(n^2)$

• Phase 1: $O(n^2)$ $-$ each add must find the right place
• Phase 2: $O(n)$ $-$ pop from the front each time

Heap-Sort -> $O(n\log n)$

• Phase 1: $O(n\log n)$ $-$ add takes $\log n$ time ($\times n$)
• Phase 2: $O(n\log n)$ $-$ remove_min takes $\log n$ time ($\times n$)

---

CITS2200 - Lecture 18