de.lmu.ifi.dbs.elki.utilities.datastructures.heap

Class ComparatorMinHeap<K>

java.lang.Object

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparatorMinHeap<K>

Type Parameters:

K - Key type

All Implemented Interfaces:

ObjectHeap<K>

public class ComparatorMinHeap<K>
extends java.lang.Object
implements ObjectHeap<K>

Binary heap for primitive types.

Since:

0.5.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	ComparatorMinHeap.UnsortedIter Unsorted iterator - in heap order.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Comparator<java.lang.Object>	comparator Comparator
protected int	size Current size of heap.
private static int	TWO_HEAP_INITIAL_SIZE Initial size of the 2-ary heap.
protected java.lang.Object[]	twoheap Base heap.

Constructor Summary

Constructors

Constructor and Description
ComparatorMinHeap(java.util.Comparator<? super K> comparator) Constructor, with default size.
ComparatorMinHeap(int minsize, java.util.Comparator<? super K> comparator) Constructor, with given minimum size.

Method Summary

Modifier and Type	Method and Description
void	add(K o) Add a key-value pair to the heap
void	add(K key, int max) Add a key-value pair to the heap, except if the new element is larger than the top, and we are at design size (overflow)
void	clear() Delete all elements from the heap.
private void	heapifyDown(java.lang.Object cur) Invoke heapify-down for the root object.
private void	heapifyUp(int twopos, java.lang.Object cur) Heapify-Up method for 2-ary heap.
boolean	isEmpty() Is the heap empty?
K	peek() Get the current top key
K	poll() Remove the first element
K	replaceTopElement(K reinsert) Combined operation that removes the top element, and inserts a new element instead.
int	size() Query the size
java.lang.String	toString()
ComparatorMinHeap.UnsortedIter	unsortedIter() Get an unsorted iterator to inspect the heap.

Methods inherited from class java.lang.Object

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

Field Detail

twoheap

protected java.lang.Object[] twoheap

Base heap.

size

protected int size

Current size of heap.

TWO_HEAP_INITIAL_SIZE

private static final int TWO_HEAP_INITIAL_SIZE

Initial size of the 2-ary heap.

See Also:

Constant Field Values

comparator

protected java.util.Comparator<java.lang.Object> comparator

Comparator

Constructor Detail

ComparatorMinHeap

public ComparatorMinHeap(java.util.Comparator<? super K> comparator)

Constructor, with default size.

Parameters:

comparator - Comparator

ComparatorMinHeap

public ComparatorMinHeap(int minsize,
                         java.util.Comparator<? super K> comparator)

Constructor, with given minimum size.

Parameters:

minsize - Minimum size

comparator - Comparator

Method Detail

clear

public void clear()

Description copied from interface: ObjectHeap

Delete all elements from the heap.

Specified by:

clear in interface ObjectHeap<K>

size

public int size()

Description copied from interface: ObjectHeap

Query the size

Specified by:

size in interface ObjectHeap<K>

Returns:

Size

isEmpty

public boolean isEmpty()

Description copied from interface: ObjectHeap

Is the heap empty?

Specified by:

isEmpty in interface ObjectHeap<K>

Returns:

true when the size is 0.

add

public void add(K o)

Description copied from interface: ObjectHeap

Add a key-value pair to the heap

Specified by:

add in interface ObjectHeap<K>

Parameters:

o - Key

add

public void add(K key,
                int max)

Description copied from interface: ObjectHeap

Add a key-value pair to the heap, except if the new element is larger than the top, and we are at design size (overflow)

Specified by:

add in interface ObjectHeap<K>

Parameters:

key - Key

max - Maximum size of heap

replaceTopElement

public K replaceTopElement(K reinsert)

Description copied from interface: ObjectHeap

Combined operation that removes the top element, and inserts a new element instead.

Specified by:

replaceTopElement in interface ObjectHeap<K>

Parameters:

reinsert - New element to insert

Returns:

Previous top element of the heap

heapifyUp

private void heapifyUp(int twopos,
                       java.lang.Object cur)

Heapify-Up method for 2-ary heap.

Parameters:

twopos - Position in 2-ary heap.

cur - Current object

poll

public K poll()

Description copied from interface: ObjectHeap

Remove the first element

Specified by:

poll in interface ObjectHeap<K>

Returns:

Top element

heapifyDown

private void heapifyDown(java.lang.Object cur)

Invoke heapify-down for the root object.

Parameters:

cur - Object to insert.

peek

public K peek()

Description copied from interface: ObjectHeap

Get the current top key

Specified by:

peek in interface ObjectHeap<K>

Returns:

Top key

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

unsortedIter

public ComparatorMinHeap.UnsortedIter unsortedIter()

Description copied from interface: ObjectHeap

Get an unsorted iterator to inspect the heap.

Specified by:

unsortedIter in interface ObjectHeap<K>

Returns:

Iterator