NobleBlocks

Research indexJournal article

Explaining binomial heaps

Hinze

Journal of Functional Programming1 Jan 1999Open access

NobleIDark:/48914/w1/20260523/EBF5A954DOI10.1017/s0956796899003317

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.

Discussion

Citations

Topics

More

Suggest a correction or report