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.
Last updated
Was this helpful?
A priority queue is a special type of queue in data structure where each element is associated with a priority.
Last updated
Was this helpful?
Randomized queue. Remove a random item.
Priority queue. Remove the largest (or smallest) item.
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
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]
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
