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) |
Heap
interface within Java's for( ... )
construct.
Specifically, this allows you to iterate over the entries in the heap.getEntries
, {@link
org.teneighty.heap.Heap#getKeys()} , {@link
org.teneighty.heap.Heap#getValues()} ) now correctly implement {@link
java.util.Collection#hashCode()} and {@link
java.util.Collection#equals(Object)}.Heap
instances. In order to test any heap
implementation, you need only extend this class and implement one
method (a method that returns an empty heap, as it were).equals(Object)
and
hashCode()
, according to the definitions in the
JavaDocs.PairingHeap
no longer implements {@link
java.lang.Cloneable}.PairingHeap
iteration code
logic that (sometimes) caused incomplete iteration. The new iteration
code is also much cleaner and simpler.PairingHeap
, FibonacciHeap
,
LeftistHeap
, and BinomialHeap
has been
properly encapsulated/hidden from subclasses. (These classes still
suffer, to a large degree, from the brittle base class problem, but
this is one step in making them more robust.)java.util
package (I prefer to keep them private).SuppressWarning
attributes to shut
the compiler up about erased casts, where necessary.SkewHeap
.
PairingHeap
and FibonacciHeap
will have higher performance than both the LeftistHeap
and BinomialHeap
, which would in turn be faster than the
BinaryHeap
and SkewHeap
. In practice,
maintaining the more complicated bookkeeping necessitated by the more
advanced data structures takes a constant but non-trivial amount of
time. In the face of very small datasets, the theoretically lower
performance implementations actually perform better, since they
require little or no overhead.src/test
directory, there is a small
JUnit test case called PerformanceTest
. This test allows
you to control the ratio of different types of calls as well as
problem size. From the matrix above, you can see that different heaps
are best at doing different types of operations: If you're doing lots
and lots of getMinimum
calls, you probably don't want to
to use a BinomialHeap
. On the other hand, a BinomialHeap
might make perfect sense if you're doing lots of decreaseKey
calls. Examine your problem (or the algorithm you're implementing) to
determine the ratio of operations. Plug these ratios (and a problem
size) into the test case and run it. This will give you the best idea
of which implementation to use.PerformanceTest
to make any one implementation look "the best".
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.
java.util.Collection
?
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).
long
s 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...
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.)
XXXHeap
's equals
(and hashCode
) method run so slowly? O(n2)
operation (where n
is the size of the two heaps).
BinaryHeap
no longer supports
removing entries via the Collection-view objects?
TwoThreeHeap
?
equals
and hashCode
?
Iterable
interface, etc.).
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: