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

Class TiedTopBoundedHeap<E>

java.lang.Object

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

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.TopBoundedHeap<E>

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.TiedTopBoundedHeap<E>

Type Parameters:

E - Object type

public class TiedTopBoundedHeap<E>
extends TopBoundedHeap<E>

A size-limited heap similar to TopBoundedHeap, discarding elements with the highest value. However, this variation keeps a list of tied elements.

Since:

0.4.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	TiedTopBoundedHeap.UnorderedIter Unordered heap iterator class.

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.List<E>	ties List to keep ties in.

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

maxsize

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

comparator, queue, size

Constructor Summary

Constructors

Constructor and Description
TiedTopBoundedHeap(int maxsize) Constructor for Comparable objects.
TiedTopBoundedHeap(int maxsize, java.util.Comparator<? super E> comparator) Constructor with comparator.

Method Summary

Modifier and Type	Method and Description
void	clear() Clear the heap.
protected void	handleOverflow(E e) Handle an overflow in the structure.
E	peek() Peek at the top element.
E	poll() Remove the top element.
E	replaceTopElement(E e) Combined operation that removes the top element, and inserts a new element instead.
int	size() Get the heap size.
TiedTopBoundedHeap.UnorderedIter	unorderedIter() Get an unordered heap iterator.

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

add, getMaxSize

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

checkHeap, heapifyDown, heapifyUp, heapModified, isEmpty, removeAt, resize

Methods inherited from class java.lang.Object

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

Field Detail

ties

private java.util.List<E> ties

List to keep ties in.

Constructor Detail

TiedTopBoundedHeap

public TiedTopBoundedHeap(int maxsize,
                          java.util.Comparator<? super E> comparator)

Constructor with comparator.

Parameters:

maxsize - Maximum size of heap (unless tied)

comparator - Comparator

TiedTopBoundedHeap

public TiedTopBoundedHeap(int maxsize)

Constructor for Comparable objects.

Parameters:

maxsize - Maximum size of heap (unless tied)

Method Detail

size

public int size()

Description copied from class: Heap

Get the heap size.

Overrides:

size in class Heap<E>

Returns:

Heap size

clear

public void clear()

Description copied from class: Heap

Clear the heap.

Overrides:

clear in class Heap<E>

peek

public E peek()

Description copied from class: Heap

Peek at the top element.

Overrides:

peek in class Heap<E>

Returns:

Top element.

poll

public E poll()

Description copied from class: Heap

Remove the top element.

Overrides:

poll in class Heap<E>

Returns:

Top element.

replaceTopElement

public E replaceTopElement(E e)

Description copied from class: Heap

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

Overrides:

replaceTopElement in class Heap<E>

Parameters:

e - New element to insert

Returns:

Previous top element of the heap

handleOverflow

protected void handleOverflow(E e)

Description copied from class: TopBoundedHeap

Handle an overflow in the structure. This function can be overridden to get overflow treatment.

Overrides:

handleOverflow in class TopBoundedHeap<E>

Parameters:

e - Overflowing element.

unorderedIter

public TiedTopBoundedHeap.UnorderedIter unorderedIter()

Get an unordered heap iterator.

Overrides:

unorderedIter in class Heap<E>

Returns:

Iterator.