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

Class UpdatableHeap<O>

java.lang.Object

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap<O>

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap<O>

Type Parameters:

O - object type

Direct Known Subclasses:

TopBoundedUpdatableHeap

public class UpdatableHeap<O>
extends Heap<O>

A heap as used in OPTICS that allows updating entries.

Author:

Erich Schubert

Nested Class Summary

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap

Heap.UnorderedIter

Field Summary

Fields

Modifier and Type	Field and Description
protected static int	IN_TIES Constant for "in ties list", for tied heaps.
protected gnu.trove.map.TObjectIntMap<Object>	index Holds the indices in the heap of each element.
protected static int	NO_VALUE Constant for "not in heap".

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

comparator, queue, size

Constructor Summary

Constructors

Constructor and Description
UpdatableHeap() Simple constructor with default size.
UpdatableHeap(Comparator<? super O> comparator) Constructor with comparator.
UpdatableHeap(int size) Constructor with predefined size.
UpdatableHeap(int size, Comparator<? super O> comparator) Constructor with predefined size and comparator.

Method Summary

Modifier and Type	Method and Description
void	add(O e) Add an element to the heap.
void	clear() Clear the heap.
protected boolean	heapifyDownComparable(int ipos, Object reinsert) Execute a "Heapify Downwards" aka "SiftDown".
protected boolean	heapifyDownComparator(int ipos, Object cur) Execute a "Heapify Downwards" aka "SiftDown".
protected void	heapifyUpComparable(int pos, Object elem) Execute a "Heapify Upwards" aka "SiftUp".
protected void	heapifyUpComparator(int pos, Object cur) Execute a "Heapify Upwards" aka "SiftUp".
protected void	offerAt(int pos, O e) Offer element at the given position.
O	poll() Remove the top element.
protected O	removeAt(int pos) Remove the element at the given position.
O	removeObject(O e) Remove the given object from the queue.
O	replaceTopElement(O e) Combined operation that removes the top element, and inserts a new element instead.

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

checkHeap, heapifyDown, heapifyUp, heapModified, isEmpty, peek, resize, size, unorderedIter

Methods inherited from class java.lang.Object

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

Field Detail

NO_VALUE

protected static final int NO_VALUE

Constant for "not in heap".

See Also:

Constant Field Values

IN_TIES

protected static final int IN_TIES

Constant for "in ties list", for tied heaps.

See Also:

Constant Field Values

index

protected final gnu.trove.map.TObjectIntMap<Object> index

Holds the indices in the heap of each element.

Constructor Detail

UpdatableHeap

public UpdatableHeap()

Simple constructor with default size.

UpdatableHeap

public UpdatableHeap(int size)

Constructor with predefined size.

Parameters:

size - Size

UpdatableHeap

public UpdatableHeap(Comparator<? super O> comparator)

Constructor with comparator.

Parameters:

comparator - Comparator

UpdatableHeap

public UpdatableHeap(int size,
                     Comparator<? super O> comparator)

Constructor with predefined size and comparator.

Parameters:

size - Size

comparator - Comparator

Method Detail

clear

public void clear()

Description copied from class: Heap

Clear the heap.

Overrides:

clear in class Heap<O>

add

public void add(O e)

Description copied from class: Heap

Add an element to the heap.

Overrides:

add in class Heap<O>

Parameters:

e - Element to add

offerAt

protected void offerAt(int pos,
                       O e)

Offer element at the given position.

Parameters:

pos - Position

e - Element

removeAt

protected O removeAt(int pos)

Description copied from class: Heap

Remove the element at the given position.

Overrides:

removeAt in class Heap<O>

Parameters:

pos - Element position.

Returns:

Element that was at this position.

removeObject

public O removeObject(O e)

Remove the given object from the queue.

Parameters:

e - Object to remove

Returns:

Existing entry

poll

public O poll()

Description copied from class: Heap

Remove the top element.

Overrides:

poll in class Heap<O>

Returns:

Top element.

replaceTopElement

public O replaceTopElement(O e)

Description copied from class: Heap

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

Overrides:

replaceTopElement in class Heap<O>

Parameters:

e - New element to insert

Returns:

Previous top element of the heap

heapifyUpComparable

protected void heapifyUpComparable(int pos,
                                   Object elem)

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

Overrides:

heapifyUpComparable in class Heap<O>

Parameters:

pos - insertion position

elem - Element to insert

heapifyUpComparator

protected void heapifyUpComparator(int pos,
                                   Object cur)

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

Overrides:

heapifyUpComparator in class Heap<O>

Parameters:

pos - insertion position

cur - Element to insert

heapifyDownComparable

protected boolean heapifyDownComparable(int ipos,
                                        Object reinsert)

Description copied from class: Heap

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

Overrides:

heapifyDownComparable in class Heap<O>

Parameters:

ipos - re-insertion position

reinsert - Object to reinsert

Returns:

true when the order was changed

heapifyDownComparator

protected boolean heapifyDownComparator(int ipos,
                                        Object cur)

Description copied from class: Heap

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

Overrides:

heapifyDownComparator in class Heap<O>

Parameters:

ipos - re-insertion position

cur - Object to reinsert

Returns:

true when the order was changed