Skip to content
Implementation of a functional version of a Brodal queue in Scala
Scala
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.

Files

Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
.gitignore
LICENCE
README.md
build.sbt

README.md

Functional Brodal Queues

Implementation of a purely functional version of binomial queues and Brodal queues in Scala.

Brodal queues are priority queues with worst-case optimal time complexity - O(1) for findMin, insert and meld (merge) and O(log n) for deleteMin. The adaptation to a purely functional structure was made according to Brodal and Okasaki in Optimal Purely Functional Priority Queues (1996): by incrementally introducing tweaks to binomial queues, a simpler priority queue implementation. The functional versions implemented here maintain the asymptotic bounds of their imperative counterparts.

A presentation about binomial queues and this data structure can be found here.

Copyright

Copyright (c) 2013 Rui Gonçalves. See LICENSE for details.

You can’t perform that action at this time.