\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt}
This material takes 1:15

Heaps

Shortest path/MST motivation. Discuss Prim/Dijkstra algorithm.

Note: lots more decrease-key than delete.

Response: balancing

$d$-heaps:

Fibonacci Heaps

Fredman-Tarjan, JACM 34(3) 1987.

http://www.acm.org/pubs/citations/journals/jacm/1987-34-3/p596-fredman/

Key principles:

Lazy approach:

Problem?

Solution: Use your work to simplify

Benefit: on delete-min, new min is child of current root

Can we be lazy and simultaneously prepare for future laziness?

Generalize

induction: if only link heaps of same degree, than any degree-$d$ heap has $2^{d}$ nodes.

Consolidation algorithm for list of arbitrary HOTS

Combine with lazy insert

Heap ordered trees implementation

Insert solution idea: adversary has to do many insertions to make consolidation expensive.

Result: $O(1)$ amortized insert, $O(\log n)$ amortized delete

What about decrease-key?

“saving private ryan”

Analysis: must show

Second potential function: number of mark bits.

Analysis of tree size:

Practical?

Minimum Spanning Tree

minimum spanning tree (and shortest path) easy in $O(m+n\log n)$.

More sophisticated MST:

Formal:

Analysis:

Remarks: