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.

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 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, Comparator<? super E> comparator) Constructor with comparator.

Method Summary

Methods

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, heapifyDownComparable, heapifyDownComparator, heapifyUp, heapifyUpComparable, heapifyUpComparator, 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 List<E> ties

List to keep ties in.

Constructor Detail

TiedTopBoundedHeap

public TiedTopBoundedHeap(int maxsize,
                  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.