Page cover

What's Priority Queue & Implementation

A priority queue is a special type of queue in data structure where each element is associated with a priority.

Randomized queue. Remove a random item.

Priority queue. Remove the largest (or smallest) item.

operation
arguments
return value

insert

P

insert

Q

insert

E

remove max

Q

insert

X

insert

A

insert

M

remove max

X

insert

P

insert

L

insert

E

remove max

P

Priority Queue Applications

  • Event-driven simulation. [customers in a line, colliding particles]

  • Numerical computation. [reducing roundoff error]

  • Data compression. [Huffman codes]

  • Graph searching. [Dijkstra's algorithm, Prim's algorithm]

  • Number theory. [sum of powers]

  • Artificial intelligence. [A* search]

  • Statistics. [maintain largest M values in a sequence]

  • Operating systems. [load balancing, interrupt handling]

  • Discrete optimization. [bin packing, scheduling]

  • Spam filtering. [Bayesian spam filter]

Priority queue client example

Challenge Find the largest M items in a stream of N items. [N huge, M large]

・Fraud detection: isolate $$ transactions.

・File maintenance: find the biggest files or directories.

Constraint Not enough memory to store N items.

Slides # 6, 7, 8

Last updated

Was this helpful?