Package org.jheaps

Interface DoubleEndedAddressableHeap<K,V>

Type Parameters:

K - the type of keys maintained by this heap

V - the type of values maintained by this heap

All Superinterfaces:

AddressableHeap<K,V>

All Known Subinterfaces:

MergeableDoubleEndedAddressableHeap<K,V>

All Known Implementing Classes:

ReflectedFibonacciHeap, ReflectedHeap, ReflectedPairingHeap

public interface DoubleEndedAddressableHeap<K,V>
extends AddressableHeap<K,V>

A double-ended heap whose elements can be addressed using handles. An insert operation returns a AddressableHeap.Handle which can later be used in order to manipulate the element, such as decreasing its key, increasing its key, or deleting it. Storing the handle externally is the responsibility of the user.

Author:

Dimitrios Michail

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	DoubleEndedAddressableHeap.Handle<K,V>	A double-ended heap element handle.

Method Summary

Modifier and Type	Method	Description
DoubleEndedAddressableHeap.Handle<K,V>	deleteMax()	Delete and return an element with the maximum key.
DoubleEndedAddressableHeap.Handle<K,V>	deleteMin()	Delete and return an element with the minimum key.
DoubleEndedAddressableHeap.Handle<K,V>	findMax()	Find an element with the maximum key.
DoubleEndedAddressableHeap.Handle<K,V>	findMin()	Find an element with the minimum key.
DoubleEndedAddressableHeap.Handle<K,V>	insert(K key)	Insert a new element into the heap with a null value.
DoubleEndedAddressableHeap.Handle<K,V>	insert(K key, V value)	Insert a new element into the heap.

Methods inherited from interface org.jheaps.AddressableHeap

clear, comparator, isEmpty, size

Method Detail

insert

DoubleEndedAddressableHeap.Handle<K,V> insert(K key,
                                                    V value)

Insert a new element into the heap.

Specified by:

insert in interface AddressableHeap<K,V>

Parameters:

key - the element's key

value - the element's value

Returns:

a handle for the newly added element

insert

DoubleEndedAddressableHeap.Handle<K,V> insert(K key)

Insert a new element into the heap with a null value.

Specified by:

insert in interface AddressableHeap<K,V>

Parameters:

key - the element's key

Returns:

a handle for the newly added element

findMin

DoubleEndedAddressableHeap.Handle<K,V> findMin()

Find an element with the minimum key.

Specified by:

findMin in interface AddressableHeap<K,V>

Returns:

a handle to an element with minimum key

deleteMin

DoubleEndedAddressableHeap.Handle<K,V> deleteMin()

Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. After the element is deleted the handle is invalidated and only method AddressableHeap.Handle.getKey() and AddressableHeap.Handle.getValue() can be used.

Specified by:

deleteMin in interface AddressableHeap<K,V>

Returns:

a handle to the deleted element with minimum key

findMax

DoubleEndedAddressableHeap.Handle<K,V> findMax()

Find an element with the maximum key.

Returns:

an element with the maximum key

Throws:

NoSuchElementException - if the heap is empty

deleteMax

DoubleEndedAddressableHeap.Handle<K,V> deleteMax()

Delete and return an element with the maximum key. If multiple such elements exists, only one of them will be deleted.

Returns:

the deleted element with the maximum key

Throws:

NoSuchElementException - if the heap is empty