Package org.jheaps
Interface MergeableHeap<K>
- Type Parameters:
K
- the type of keys maintained by this heap
- All Superinterfaces:
Heap<K>
- All Known Implementing Classes:
BinaryTreeSoftHeap
A heap that allows melding with another heap.
The second heap becomes empty and unusable after the meld operation, meaning
than further insertions are not possible and will throw an
IllegalStateException
.
A ClassCastException
will be thrown if the two heaps are not of the
same type. Moreover, the two heaps need to use the same comparators. If only
one of them uses a custom comparator or both use custom comparators but are
not the same by equals, an IllegalArgumentException
is
thrown.
Note that all running time bounds on mergeable heaps are valid assuming that the user does not perform cascading melds on heaps such as:
d.meld(e); c.meld(d); b.meld(c); a.meld(b);The above scenario, although efficiently supported by using union-find with path compression, invalidates the claimed bounds.
-
Method Summary
Modifier and TypeMethodDescriptionvoid
meld
(MergeableHeap<K> other) Meld a heap into the current heap.
-
Method Details
-
meld
Meld a heap into the current heap. After the operation theother
heap will be empty and will not permit further insertions.- Parameters:
other
- a merge-able heap- Throws:
ClassCastException
- ifother
is not compatible with this heapIllegalArgumentException
- ifother
does not have a compatible comparator
-