Unit 3: Efficient Priority Queues

This unit covers:

• Tournament trees
• LP heaps
• Quake heaps

Material

• slides

• lecture notes

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

• Video 3-2 (2026-06-01): Tournament Trees

• Video 3-3 (2026-06-01): Lazy Partition Heaps

• Video 3-4 (2026-06-01): Fibonacci Heaps – Informal Overview

• Video 3-5 (2026-06-01): Quake Heaps Overview

• Video 3-6 (2026-06-02): Quake Heaps Operations

• Video 3-7 (2026-06-02): Quake Heaps Analysis

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 constants in the potential function fixed, and the gap of how to do meld in O(1) time plugged by Tamio-Vesa Nakajima).

• 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 implementation does not support fast meld.)

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

• Brodal, Advanced Data Structures, 2015

---

Unit 2  ⋅  Syllabus  ⋅  Unit 4