Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-24T02:38:56.790Z Has data issue: false hasContentIssue false
  • English
  • Français

Explaining binomial heaps

Published online by Cambridge University Press:  01 January 1999

RALF HINZE
RALF HINZE
Affiliation:
Institut für Informatik III, Universität Bonn, Römerstraße 164, 53117 Bonn, Germany (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
FUNCTIONAL PEARL
Information
Journal of Functional Programming , Volume 9 , Issue 1 , January 1999 , pp. 93 - 104
Copyright
© 1999 Cambridge University Press
Supplementary material: Link

Hinze Supplementary Material

/JFP/online/jfpvol9-1/hinze/index.html
Link
Submit a response

Discussions

No Discussions have been published for this article.