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.

5MB

PriorityQueues.pdf

pdf

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

Exercise