This package contains the teneighty.org heap collection.

The table below summarizes the available implementations:
  Construction {@linkplain org.teneighty.heap.Heap#insert(Object, Object) Insert} {@linkplain org.teneighty.heap.Heap#getMinimum() Get Minimum} {@linkplain org.teneighty.heap.Heap#extractMinimum() Extract Minimum} {@linkplain org.teneighty.heap.Heap#delete(org.teneighty.heap.Heap.Entry) Delete} {@linkplain org.teneighty.heap.Heap#decreaseKey(org.teneighty.heap.Heap.Entry, Object) Decrease Key} {@linkplain org.teneighty.heap.Heap#union(Heap)} {@linkplain java.lang.Iterable Iteration} {@linkplain java.io.Serializable Serialization} {@linkplain org.teneighty.heap.Heap#equals(Object) Equality}
{@link org.teneighty.heap.BinaryHeap} θ(1) θ(log n) θ(1) θ(log n) θ(log n) θ(log n) θ(n + m) θ(n) θ(n) θ(n2)
{@link org.teneighty.heap.BinomialHeap} θ(1) O(log n) O(log n) θ(log n) O(log n) θ(log n) O(log (n + m)) θ(n) θ(n log n) O(n2)
{@link org.teneighty.heap.LeftistHeap} θ(1) O(log n) θ(1) O(log n) O(log n) O(log n) O(log n) θ(n) θ(n log n) O(n2)
{@link org.teneighty.heap.FibonacciHeap} θ(1) θ(1) θ(1) O(log n)† O(log n)† θ(1)† θ(1) θ(n) θ(n) O(n2)
{@link org.teneighty.heap.PairingHeap} θ(1) O(1)† θ(1) O(log n)† Ω(log log n), 2O(√log log n) Ω(log log n), 2O(√log log n) O(1)† θ(n) θ(n) O(n2)
{@link org.teneighty.heap.SkewHeap} θ(1) O(log n)† θ(1) O(log n)† O(log n)† O(log n)† O(log (n + m))† θ(n) θ(n) O(n2)
† = Amortized complexity.

Frequently Asked Questions

  1. What's new in the latest release (2.0.0.0)?
    There are several new features and bug fixes. In no particular order:

  2. Which heap implementation should I use? ...or... Which heap implementation is the best?
    This depends on your problem (i.e. which methods of the heap interface will you be using, how often etc.), the size of your dataset, your virtual machine, and your hardware. Several things to keep in mind:

  3. Why have a Heap package when the Java Collection Framework contains the {@link java.util.Queue} interface?
    The Heap ADT is fundamentally different from the Queue ADT. The basic Queue ADT is add, peek, and removeFirst (and other dumb utility methods); heaps provide all this, but with the ability to {@linkplain org.teneighty.heap.Heap#delete(org.teneighty.heap.Heap.Entry) delete an arbitrary entry}, {@linkplain org.teneighty.heap.Heap#decreaseKey(org.teneighty.heap.Heap.Entry, Object) decrease the key of an arbitrary entry}, and {@linkplain org.teneighty.heap.Heap#union(Heap) union/meld two heaps together} (and other lame utility methods). These additional operations should generally be supported in sublinear time by a heap, whereas they are generally not available for queues or must be performed externally at significant expense. Every CS student learns that the job of creating a queue is reduced to the one of creating a heap - with a binary heap implemenation e.g., one can easily create a priority, FIFO, or LIFO queue. However, the ability to reduce the problem of implementing a queue to the problem of implenting of a heap does not mean they are the same thing.

  4. How come the Heap interface does not extends {@link java.util.Map}?
    For the same reason as above: Maps/Dictionarys and Heaps are fundamentally different ADTs.

  5. Why does the Heap interface not extend java.util.Collection?
    This is a legitimate question. The main reason is that the items passed to delete and decreaseKey are allocated internally by the creating heap and generally contain heap/implementation specific information - they are, in fact, the objects returned from the insert method. Contrast this to a standard Collection, in which the objects to be removed (or retained) are, in fact, not returned from the add/insert method, but rather allocated externally. The heap interface would thus have some ill-defined methods and generally be less elegant (IMHO).

  6. Isn't this re-inventing the wheel? I mean, surely, someone else has implemented these stupid things?
    Well, yes, there are implementations of these things out there. However, none that I have seen have a unified, Java Collection Framework-esque interface or bridges to said Framework (this package does). Furthermore, most of the implementations out there were done for fun/academic purposes; as such, they usually impose lame constraints (e.g. only longs can be keys) or have other highly annoying problems (memory leaks, no documentation, no unit tests, code that fails unit tests, no serialization support, etc.). The point of this package is to avoid/remedy those problems. It's turned out to have been a surprising amount of work...

  7. Why does the {@link org.teneighty.heap.Comparators} class contain the {@link org.teneighty.heap.Comparators#invertComparator(Comparator)} method when such a method ({@link java.util.Collections#reverseOrder(Comparator)}) already exists in {@link java.util.Collections}?
    The implementation in java.util.Collections is implemented in a very weird way, such that passing a null value will result in a reversed natural order comparator. I found this a bit goofy. Also, the returned object does not properly implement hashCode or equals, which annoys the hell out of me. Lastly, I think the term "invert" more properly describes what's going on. (You invert a function, but reverse a sequence. Put another way, an inverted comparator will resulted in a reversed object collection. And, yes, I'm a jerk when it comes to semantics. But what do you want from me? I was a classics major.)

  8. What if I want an inverted natural order comparator?
    Well, you could create a {@link org.teneighty.heap.NaturalOrderComparator} and then invert it...

  9. Why does XXXHeap's equals (and hashCode) method run so slowly?
    Unfortunately, there is no way to quickly compare to different heaps, even of the same implementation. (Even if they contain the same set of key/value pairs, heaps of the same implementation may have vastly different internal structures.) Thus, the current equals method for most heaps works by comparing the entry sets, which is an O(n2) operation (where n is the size of the two heaps).

  10. How come the BinaryHeap no longer supports removing entries via the Collection-view objects?
    See the class docs for {@link org.teneighty.heap.BinaryHeap}. There's a decent discussion there.

  11. What ever happened to the mythical TwoThreeHeap?
    It was filled with bugs, and despite it's theoretically higher performance, was routinely spanked by the Fibonacci and Pairing heaps.

  12. What is your obsession with overriding equals and hashCode?
    This is not something I can rationally explain. It's just something I think must be done.

  13. I've found a bug. What should I do?
    You can report bugs here: http://code.google.com/p/java-heaps/issues/list.

  14. Under what license is this software distributed?
    The teneighty.org heap collection is distributed under the very liberal MIT License. (This is known as the X or X11 License in some circles.) You can incorporate this package, in source or binary forms, with or without modification, into open or closed source projects. The MIT License is a copycenter style license (c.f. copyright and copyleft), as in: "Take it down to the copy center and make as many copies as you want."

  15. Why did you create this package?
    Heaps are fun and useful! Also, in my college days, my roommate and I did a fairly cool project on maximum flows. I've been playing with heaps ever since.

  16. Why did you use Java 1.6?
    Because it was there.

  17. Is a pre-1.6 version available?
    This package will compile and pass all unit tests against Java 1.5 as well. There is, however, no version available for pre-Java 1.5. (You could do this by simply removing all the 1.5/1.6 features, e.g. generic, enums, the Iterable interface, etc.).

  18. What's next for the Heap Collection?
    I am currently implementing and testing a thin heap, a spiffy new data structure from Robert Tarjan and Haim Kaplan. The fat heap should offer superior performance for a wide range of problems.

    Also in the works in the notion of a mapped heap - one which provides not only all the wonders of a regular heap, but it also capable of doing lookup by key in sublinear time. I am attempting to implement a bi-parental heap and/or van Emde-Boas heap as the first two mapped heaps.

    Finally, I'm working on a C# port/re-implementation of this package, because C# is pretty badass (even if it is backed by the Evil Empire). Should be coming soon...

 

A few quick thanks:

@author Fran Lattanzio