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

Class IntegerHeap

java.lang.Object

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

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

Direct Known Subclasses:

IntegerMaxHeap, IntegerMinHeap

public abstract class IntegerHeap
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 int[]	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
IntegerHeap(int size) Constructor with initial capacity.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(int key) Add a key-value pair to the heap
void	add(int 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(int o1, int o2) Compare two objects
protected void	ensureValid() Repair the heap
protected boolean	heapifyDown(int ipos, int curkey) Execute a "Heapify Downwards" aka "SiftDown".
protected void	heapifyUp(int pos, int curkey) Execute a "Heapify Upwards" aka "SiftUp".
int	peek() Get the current top key
int	poll() Remove the first element
protected int	removeAt(int pos) Remove the element at the given position.
int	replaceTopElement(int 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 int[] queue

Heap storage: queue

Constructor Detail

IntegerHeap

public IntegerHeap(int size)

Constructor with initial capacity.

Parameters:

size - initial capacity

Method Detail

add

public void add(int key)

Add a key-value pair to the heap

Parameters:

key - Key

add

public void add(int 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 int replaceTopElement(int 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 int peek()

Get the current top key

Returns:

Top key

poll

public int poll()

Remove the first element

Returns:

Top element

ensureValid

protected void ensureValid()

Repair the heap

removeAt

protected int removeAt(int pos)

Remove the element at the given position.

Parameters:

pos - Element position.

Returns:

Removed element

heapifyUp

protected void heapifyUp(int pos,
             int curkey)

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

Parameters:

pos - insertion position

curkey - Current key

heapifyDown

protected boolean heapifyDown(int ipos,
                  int 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(int o1,
           int o2)

Compare two objects