Package org.jheaps

Interface AddressableHeap<K,V>

Type Parameters:

K - the type of keys maintained by this heap

V - the type of values maintained by this heap

All Known Subinterfaces:

DoubleEndedAddressableHeap<K,V>, MergeableAddressableHeap<K,V>, MergeableDoubleEndedAddressableHeap<K,V>

All Known Implementing Classes:

BigIntegerRadixAddressableHeap, BinaryArrayAddressableHeap, BinaryTreeAddressableHeap, BinaryTreeSoftAddressableHeap, CostlessMeldPairingHeap, DaryArrayAddressableHeap, DaryTreeAddressableHeap, DoubleRadixAddressableHeap, FibonacciHeap, HollowHeap, IntegerRadixAddressableHeap, LeftistHeap, LongRadixAddressableHeap, PairingHeap, RankPairingHeap, ReflectedFibonacciHeap, ReflectedHeap, ReflectedPairingHeap, SimpleFibonacciHeap, SkewHeap

public interface AddressableHeap<K,V>

A 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, 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	AddressableHeap.Handle<K,V>	A heap element handle.

Method Summary

Modifier and Type	Method	Description
void	clear()	Clear all the elements of the heap.
Comparator<? super K>	comparator()	Returns the comparator used to order the keys in this AddressableHeap, or null if this heap uses the natural ordering of its keys.
AddressableHeap.Handle<K,V>	deleteMin()	Delete and return an element with the minimum key.
AddressableHeap.Handle<K,V>	findMin()	Find an element with the minimum key.
AddressableHeap.Handle<K,V>	insert(K key)	Insert a new element into the heap with a null value.
AddressableHeap.Handle<K,V>	insert(K key, V value)	Insert a new element into the heap.
boolean	isEmpty()	Returns true if this heap is empty.
long	size()	Returns the number of elements in the heap.

Method Detail

comparator

Comparator<? super K> comparator()

Returns the comparator used to order the keys in this AddressableHeap, or null if this heap uses the natural ordering of its keys.

Returns:

the comparator used to order the keys in this heap, or null if this addressable heap uses the natural ordering of its keys

insert

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

Insert a new element into the heap.

Parameters:

key - the element's key

value - the element's value

Returns:

a handle for the newly added element

insert

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

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

Parameters:

key - the element's key

Returns:

a handle for the newly added element

findMin

AddressableHeap.Handle<K,V> findMin()

Find an element with the minimum key.

Returns:

a handle to an element with minimum key

deleteMin

AddressableHeap.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.

Returns:

a handle to the deleted element with minimum key

isEmpty

boolean isEmpty()

Returns true if this heap is empty.

Returns:

true if this heap is empty, false otherwise

size

long size()

Returns the number of elements in the heap.

Returns:

the number of elements in the heap

clear

void clear()

Clear all the elements of the heap. After calling this method all handles should be considered invalidated and the behavior of methods AddressableHeap.Handle.decreaseKey(Object) and AddressableHeap.Handle.delete() is undefined.