资 源 简 介
Following, at least initially, a paper by Brodal and Okasaki, we aim to provide java developers with an efficient, purely functional/persistent heap (priority queue) structure with worst-case (not amortized) guarantees. By "functional" we mean that all operations are queries with no side-effects. Persistence implies that no "operation" (query) modifies a view that another client may hold. Structure should be optimally reused to avoid excessive copying and memory wastage.
Note that this project may end up having Clojure code either for testing or as the eventual implementation. It could also be merged with some part of the Clojure project if folks find (make) it useful.
Heaps can be very useful for semi-lazy sorting, for one thing. It is hoped that this code, though, can also help with problems such as A-Star and Branch-And-Bound.
One challenge will be to implement decreaseKey()/delete() in a functional setting, but it"s important for
