de.lmu.ifi.dbs.elki.utilities.datastructures.heap
Class KNNHeap<D extends Distance<D>>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractQueue<E>
          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<DistanceResultPair<D>>
                      de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap<D>

Type Parameters:

D - distance type

All Implemented Interfaces:

Serializable, Iterable<DistanceResultPair<D>>, Collection<DistanceResultPair<D>>, Queue<DistanceResultPair<D>>

public class KNNHeap<D extends Distance<D>>
extends TiedTopBoundedHeap<DistanceResultPair<D>>

Heap used for KNN management.

See Also:

Serialized Form

Nested Class Summary

static class

KNNHeap.Comp<D extends Distance<D>> Comparator to use.

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

Heap.Itr

Field Summary

private D	maxdist Maximum distance, usually infiniteDistance
private static long	serialVersionUID Serial version

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

modCount, size

Constructor Summary

KNNHeap(int k)
Simplified constructor.

KNNHeap(int k, D maxdist)
Constructor.

Method Summary

boolean	add(D distance, DBID id) Add a distance-id pair to the heap unless the distance is too large.
int	getK() Get the K parameter ("maxsize" internally).
D	getKNNDistance() Get the distance to the k nearest neighbor, or maxdist otherwise.
D	getMaximumDistance() Get maximum distance in heap
KNNList<D>	toKNNList() Serialize to a KNNList.
ArrayList<DistanceResultPair<D>>	toSortedArrayList() Return the heap as a sorted array list, by repeated polling.

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

clear, contains, handleOverflow, iterator, peek, poll, size

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

getMaxSize, offer

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

castQueueElement, compare, compareExternal, compareExternalExternal, heapifyDown, heapifyUp, heapifyUpParent, putInQueue, removeAt, swap

Methods inherited from class java.util.AbstractQueue

add, addAll, element, remove

Methods inherited from class java.util.AbstractCollection

containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray

Field Detail

serialVersionUID

private static final long serialVersionUID

Serial version

See Also:

Constant Field Values

maxdist

private final D extends Distance<D> maxdist

Maximum distance, usually infiniteDistance

Constructor Detail

KNNHeap

public KNNHeap(int k,
               D maxdist)

Constructor.

Parameters:

k - k Parameter

maxdist - k-distance to return for less than k neighbors - usually infiniteDistance

KNNHeap

public KNNHeap(int k)

Simplified constructor. Will return null as kNN distance with less than k entries.

Parameters:

k - k Parameter

Method Detail

toSortedArrayList

public ArrayList<DistanceResultPair<D>> toSortedArrayList()

Description copied from class: Heap

Return the heap as a sorted array list, by repeated polling. This will empty the heap!

Overrides:

toSortedArrayList in class Heap<DistanceResultPair<D extends Distance<D>>>

Returns:

new array list

toKNNList

public KNNList<D> toKNNList()

Serialize to a KNNList. This empties the heap!

Returns:

KNNList with the heaps contents.

getK

public int getK()

Get the K parameter ("maxsize" internally).

Returns:

K

getKNNDistance

public D getKNNDistance()

Get the distance to the k nearest neighbor, or maxdist otherwise.

Returns:

Maximum distance

getMaximumDistance

public D getMaximumDistance()

Get maximum distance in heap

add

public boolean add(D distance,
                   DBID id)

Add a distance-id pair to the heap unless the distance is too large. Compared to the super.add() method, this often saves the pair construction.

Parameters:

distance - Distance value

id - ID number

Returns:

success code