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

Class ObjectHeap<K>

java.lang.Object

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

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

Direct Known Subclasses:

ComparableMaxHeap, ComparableMinHeap

public abstract class ObjectHeap<K>
extends AbstractHeap

Basic in-memory heap structure. This heap is built lazily: if you first add many elements, then poll the heap, it will be bulk-loaded in O(n) instead of iteratively built in O(n log n). This is implemented via a simple validTo counter.

Field Summary

Fields

Modifier and Type	Field and Description
protected Object[]	queue Heap storage: queue

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.AbstractHeap

DEFAULT_INITIAL_CAPACITY, modCount, size, validSize

Constructor Summary

Constructors

Constructor and Description
ObjectHeap(int size) Constructor with initial capacity.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(Object key) Add a key-value pair to the heap
void	add(Object 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.
protected abstract boolean	comp(Object o1, Object o2) Compare two objects
protected void	ensureValid() Repair the heap
protected boolean	heapifyDown(int ipos, Object curkey) Execute a "Heapify Downwards" aka "SiftDown".
protected void	heapifyUp(int pos, Object curkey) Execute a "Heapify Upwards" aka "SiftUp".
Object	peek() Get the current top key
Object	poll() Remove the first element
protected Object	removeAt(int pos) Remove the element at the given position.
Object	replaceTopElement(Object e) Combined operation that removes the top element, and inserts a new element instead.
protected void	resize(int requiredSize) Test whether we need to resize to have the requested capacity.

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.AbstractHeap

desiredSize, heapModified, size

Methods inherited from class java.lang.Object

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

Field Detail

queue

protected transient Object[] queue

Heap storage: queue

Constructor Detail

ObjectHeap

public ObjectHeap(int size)

Constructor with initial capacity.

Parameters:

size - initial capacity

Method Detail

add

public void add(Object key)

Add a key-value pair to the heap

Parameters:

key - Key

add

public void add(Object 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)

Parameters:

key - Key

max - Maximum size of heap

replaceTopElement

public Object replaceTopElement(Object e)

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

Parameters:

e - New element to insert

Returns:

Previous top element of the heap

peek

public Object peek()

Get the current top key

Returns:

Top key

poll

public Object poll()

Remove the first element

Returns:

Top element

ensureValid

protected void ensureValid()

Repair the heap

removeAt

protected Object removeAt(int pos)

Remove the element at the given position.

Parameters:

pos - Element position.

Returns:

Removed element

heapifyUp

protected void heapifyUp(int pos,
             Object curkey)

Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.

Parameters:

pos - insertion position

curkey - Current key

heapifyDown

protected boolean heapifyDown(int ipos,
                  Object curkey)

Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.

Parameters:

ipos - re-insertion position

curkey - Current key

Returns:

true when the order was changed

resize

protected final void resize(int requiredSize)

Test whether we need to resize to have the requested capacity.

Parameters:

requiredSize - required capacity

clear

public void clear()

Delete all elements from the heap.

Overrides:

clear in class AbstractHeap

comp

protected abstract boolean comp(Object o1,
           Object o2)

Compare two objects