org.jheaps.monotone

Class IntegerRadixHeap

java.lang.Object

org.jheaps.monotone.IntegerRadixHeap

All Implemented Interfaces:

Serializable, Heap<Integer>

public class IntegerRadixHeap
extends Object

A radix heap for (signed) integer keys. The heap stores integer keys sorted according to the natural ordering of its keys. A radix heap is a monotone heap, especially designed for algorithms (such as Dijkstra) which scan elements in order of nondecreasing keys.

This implementation uses arrays in order to store the elements. Operations insert and findMin are worst-case constant time. The cost of operation deleteMin is amortized O(logC) assuming the radix-heap contains keys in the range [0, C] or equivalently [a,a+C]. Integer values are viewed as signed numbers.

Note that this implementation is not synchronized. If multiple threads access a heap concurrently, and at least one of the threads modifies the heap structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements or changing the key of some element.) This is typically accomplished by synchronizing on some object that naturally encapsulates the heap.

Author:

Dimitrios Michail

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
IntegerRadixHeap(int minKey, int maxKey) Constructs a new heap which can store values between a minimum and a maximum key value (inclusive).

Method Summary

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

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

IntegerRadixHeap

public IntegerRadixHeap(int minKey,
                        int maxKey)

Constructs a new heap which can store values between a minimum and a maximum key value (inclusive). It is important to use the smallest key range as the heap uses O(logC) where C=maxKey-minKey+1 buckets to store elements. Moreover, the operation deleteMin requires amortized O(logC) time.

Parameters:

minKey - the non-negative minimum key that this heap supports (inclusive)

maxKey - the maximum key that this heap supports (inclusive)

Throws:

IllegalArgumentException - if the minimum key is negative

IllegalArgumentException - if the maximum key is less than the minimum key

Method Detail

findMin

public K findMin()

Find an element with the minimum key.

Specified by:

findMin in interface Heap<K>

Returns:

an element with the minimum key

insert

public void insert(K key)

Insert a key into the heap.

Specified by:

insert in interface Heap<K>

Parameters:

key - the key to insert

Throws:

IllegalArgumentException - if the key is null

IllegalArgumentException - if the key is less than the minimum allowed key

IllegalArgumentException - if the key is more than the maximum allowed key

IllegalArgumentException - if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)

deleteMin

public K deleteMin()

Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. The cost of this operation is amortized O(logC) assuming the heap contains keys in the range [0, C] or equivalently [a, a+C].

Specified by:

deleteMin in interface Heap<K>

Returns:

the deleted element with the minimum key

isEmpty

public boolean isEmpty()

Returns true if this heap is empty.

Specified by:

isEmpty in interface Heap<K>

Returns:

true if this heap is empty, false otherwise

size

public long size()

Returns the number of elements in this heap.

Specified by:

size in interface Heap<K>

Returns:

the number of elements in this heap

clear

public void clear()

Clear all the elements of this heap.

Specified by:

clear in interface Heap<K>

comparator

public Comparator<? super K> comparator()

Always returns null since this heap uses the natural ordering of its keys.

Specified by:

comparator in interface Heap<K>

Returns:

null since this heap uses the natural ordering of its keys