Unit 3: Efficient Priority Queues

This unit covers:

• Tournament trees
• LP heaps
• Quake heaps

Material

• slides

• lecture notes

• Video 3-1 (2026-04-26): Recap: Priority Queues and Binary Heaps

Further sources

The tournament tree presentation is my own; a clever loser-tree implementation for use in merging is described in

• Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching (1998)

LP Heaps are from our paper

• Brodal, Iacono, Rysgaard, Wild, Partition-based Simple Heaps (2026)

Quake heaps follow the original paper by Chan (with a mistake in the potential function fixed).

• Chan, Quake Heaps: A Simple Alternative to Fibonacci Heaps (2013)

A rather clean implementation of quake heaps can be found here:

• Elen Niedermeyer, Quake-Heaps
  (the use of LinkedList.remove is slow, though)

The short summary of Fibonacci heaps is based on the following slides

• Brodal, Advanced Data Structures, 2015

---

Unit 2  ⋅  Syllabus  ⋅  Unit 4