Package org.jheaps.monotone

Class AbstractRadixHeap<K>

java.lang.Object

org.jheaps.monotone.AbstractRadixHeap<K>

Type Parameters:

K - the key type

All Implemented Interfaces:

java.io.Serializable, Heap<K>

Direct Known Subclasses:

BigIntegerRadixHeap, DoubleRadixHeap, IntegerRadixHeap, LongRadixHeap

abstract class AbstractRadixHeap<K>
extends java.lang.Object
implements Heap<K>, java.io.Serializable

Base abstract implementation of a radix heap.

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.List<K>[]	buckets	The buckets as lists.
protected K	currentMin	The current minimum value (cached)
protected int	currentMinBucket	The current minimum value bucket (cached)
protected int	currentMinPos	The current minimum value position in bucket (cached)
protected static int	EMPTY	Denotes that a key does not belong to a bucket
protected K	lastDeletedKey	Last deleted key.
protected K	maxKey	Maximum key allowed
protected K	minKey	Minimum key allowed
private static long	serialVersionUID
protected long	size	Number of elements

Constructor Summary

Constructors

Constructor	Description
AbstractRadixHeap()	Constructor

Method Summary

Modifier and Type	Method	Description
void	clear()	Clear all the elements of this heap.
java.util.Comparator<? super K>	comparator()	Always returns null since this heap uses the natural ordering of its keys.
protected abstract int	compare(K o1, K o2)	Compares its two arguments for order.
protected int	computeBucket(K key, K minKey)	Compute the bucket of a key based on a minimum key.
K	deleteMin()	Delete and return an element with the minimum key.
private void	findAndCacheMinimum(int firstBucket)	Helper method for finding and caching the minimum.
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.
protected abstract int	msd(K a, K b)	Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.
long	size()	Returns the number of elements in this heap.

Methods inherited from class java.lang.Object

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

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

EMPTY

protected static final int EMPTY

Denotes that a key does not belong to a bucket

See Also:

Constant Field Values

buckets

protected java.util.List<K>[] buckets

The buckets as lists. We use array-lists instead of linked-lists, to be cache friendly.

size

protected long size

Number of elements

lastDeletedKey

protected K lastDeletedKey

Last deleted key. This value is used to distribute elements in the buckets. Should be initialized with the minKey value.

currentMin

protected K currentMin

The current minimum value (cached)

currentMinBucket

protected int currentMinBucket

The current minimum value bucket (cached)

currentMinPos

protected int currentMinPos

The current minimum value position in bucket (cached)

minKey

protected K minKey

Minimum key allowed

maxKey

protected K maxKey

Maximum key allowed

Constructor Detail

AbstractRadixHeap

AbstractRadixHeap()

Constructor

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:

java.lang.IllegalArgumentException - if the key is null

java.lang.IllegalArgumentException - if the key is less than the minimum allowed key

java.lang.IllegalArgumentException - if the key is more than the maximum allowed key

java.lang.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 java.util.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

compare

protected abstract int compare(K o1,
                               K o2)

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Parameters:

o1 - the first object to be compared.

o2 - the second object to be compared.

Returns:

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

computeBucket

protected int computeBucket(K key,
                            K minKey)

Compute the bucket of a key based on a minimum key.

Parameters:

key - the key

minKey - the minimum key

Returns:

the bucket where the key should go

msd

protected abstract int msd(K a,
                           K b)

Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.

Parameters:

a - the first value

b - the second value

Returns:

the most significant digit which is different or -1 if numbers are equal

findAndCacheMinimum

private void findAndCacheMinimum(int firstBucket)

Helper method for finding and caching the minimum. Assumes that the heap contains at least one element.

Parameters:

firstBucket - start looking for elements from this bucket