Journal of Functional Programming

Table of Contents - 1999 - Volume 9, Issue 01  


FUNCTIONAL PEARL

Explaining binomial heaps

RALF HINZE a1
a1 Institut für Informatik III, Universität Bonn, Römerstraße 164, 53117 Bonn, Germany (e-mail: ralf@informatik.uni-bonn.de)

Abstract

Functional programming languages are an excellent tool for teaching algorithms and data structures. This paper explains binomial heaps, a beautiful data structure for priority queues, using the functional programming language Haskell (Peterson and Hammond, 1997). We largely follow a deductive approach: using the metaphor of a tennis tournament we show that binomial heaps arise naturally through a number of logical steps. Haskell supports the deductive style of presentation very well: new types are introduced at ease, algorithms can be expressed clearly and succinctly, and Haskell's type classes allow to capture common algorithmic patterns. The paper aims at the level of an undergraduate student who has experience in reading and writing Haskell programs, and who is familiar with the concept of a priority queue.