Suggested Final Project Topics

Why they’re worth studying:  The major theoretical technique involved in quake heaps – globally re-

building a structure when it’s not in a good state – is a creative approach to designing a data structure.

This technique can be repurposed in other places and might be a great launching point for revisiting older

structures and looking for improvements.

Pairing Heaps

Fibonacci heaps have excellent amortized runtimes for their operations – in theory. In practice, the over-

head for all the pointer gymnastics renders them slower than standard binary heaps. An alternative struc-

ture called the pairing heap has worse theoretical guarantees than the Fibonacci heap, yet is significantly

simpler and faster in practice.