Suggested Final Project Topics

Why they're worth studying: Pairing heaps have an unusual property – no one actually knows how fast

they are! We've got both lower and upper bounds on their runtimes, yet it's still unknown where the actual

upper and lower bounds on the data structure lie.

Fishspears

The fishspear is a priority queue with an unusual runtime performance – the amortized cost of a deletion

is O(1), and the amortized cost of an insertion varies based on the relative size of the element removed.

Removing smaller elements tends to be much faster than removing larger elements, so if you stream ran-

dom elements through a fishspear and focus your deletion efforts primarily on small elements, the perfor-

mance will be much better than what a binary heap will be able to match.