DoubleIntegerDBIDKNNHeap (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

java.lang.Object
- de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDKNNHeap

All Implemented Interfaces:

KNNHeap
```
 class DoubleIntegerDBIDKNNHeap
extends Object
implements KNNHeap
```
Class to efficiently manage a kNN heap.

Author:

Erich Schubert

Field Summary

Fields
Modifier and Type	Field and Description
`private DoubleIntegerMaxHeap`	`heap` The main heap.
`private static int`	`INITIAL_TIES_SIZE` Initial size of ties array.
`private int`	`k` k for this heap.
`private double`	`kdist` Current maximum value.
`private int`	`numties` Number of element in ties list.
`private int[]`	`ties` List to track ties.

Constructor Summary

Constructors
Modifier Constructor and Description

protected DoubleIntegerDBIDKNNHeap(int k)
Constructor.

Constructors
Modifier	Constructor and Description
`protected`	`DoubleIntegerDBIDKNNHeap(int k)` Constructor.

Method Summary

Methods
Modifier and Type	Method and Description
`private void`	`addToTies(int id)` Ensure the ties array has capacity for at least one more element.
`void`	`clear()` Clear the heap.
`int`	`getK()` Get the K parameter ("maxsize" internally).
`double`	`getKNNDistance()` Get the distance to the k nearest neighbor, or maxdist otherwise.
`void`	`insert(DoubleDBIDPair e)` Add a distance-id pair to the heap unless the distance is too large.
`double`	`insert(double distance, DBIDRef id)` Add a distance-id pair to the heap unless the distance is too large.
`boolean`	`isEmpty()` Test if the heap is empty.
`DoubleIntegerDBIDPair`	`peek()` Peek at the largest element in the heap.
`protected double`	`peekDistance()` Peek the topmost distance.
`protected int`	`peekInternalDBID()` Peek the topmost internal ID.
`DoubleIntegerDBIDPair`	`poll()` Poll the largest element from the heap.
`protected void`	`pop()` Pop the topmost element.
`int`	`size()` Current size of heap.
`DoubleIntegerDBIDKNNList`	`toKNNList()` Serialize to a `KNNList`.
`private void`	`updateHeap(double distance, int iid)` Do a full update for the heap.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - k
```
private final int k
```
    k for this heap.
  - heap
```
private final DoubleIntegerMaxHeap heap
```
    The main heap.
  - ties
```
private int[] ties
```
    List to track ties.
  - numties
```
private int numties
```
    Number of element in ties list.
  - kdist
```
private double kdist
```
    Current maximum value.
  - INITIAL_TIES_SIZE
```
private static final int INITIAL_TIES_SIZE
```
    Initial size of ties array.
    
    See Also:
    Constant Field Values
- Constructor Detail
  - DoubleIntegerDBIDKNNHeap
```
protected DoubleIntegerDBIDKNNHeap(int k)
```
    Constructor.
    
    Parameters:
    k - Size of knn.
- Method Detail
  - getK
```
public int getK()
```
    Description copied from interface: KNNHeap
    
    Get the K parameter ("maxsize" internally).
    
    Specified by:
    
    getK in interface KNNHeap
    
    Returns:
    K
  - getKNNDistance
```
public double getKNNDistance()
```
    Description copied from interface: KNNHeap
    
    Get the distance to the k nearest neighbor, or maxdist otherwise.
    
    Specified by:
    
    getKNNDistance in interface KNNHeap
    
    Returns:
    Maximum distance
  - insert
```
public final double insert(double distance,
            DBIDRef id)
```
    Description copied from interface: KNNHeap
    
    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.
    
    Specified by:
    
    insert in interface KNNHeap
    
    Parameters:
    distance - Distance value
    id - ID number
    
    Returns:
    current k-distance
  - insert
```
public void insert(DoubleDBIDPair e)
```
    Description copied from interface: KNNHeap
    
    Add a distance-id pair to the heap unless the distance is too large. Use for existing pairs.
    
    Specified by:
    
    insert in interface KNNHeap
    
    Parameters:
    e - Existing distance pair
  - updateHeap
```
private final void updateHeap(double distance,
              int iid)
```
    Do a full update for the heap.
    
    Parameters:
    distance - Distance
    iid - Object id
  - addToTies
```
private final void addToTies(int id)
```
    Ensure the ties array has capacity for at least one more element.
    
    Parameters:
    id - Id to add
  - poll
```
public DoubleIntegerDBIDPair poll()
```
    Description copied from interface: KNNHeap
    
    Poll the largest element from the heap. This is in descending order because of the heap structure. For a convenient way to serialize the heap into a list that you can iterate in ascending order, see KNNHeap.toKNNList().
    
    Specified by:
    
    poll in interface KNNHeap
    
    Returns:
    largest element
  - pop
```
protected void pop()
```
    Pop the topmost element.
  - peek
```
public DoubleIntegerDBIDPair peek()
```
    Description copied from interface: KNNHeap
    
    Peek at the largest element in the heap.
    
    Specified by:
    
    peek in interface KNNHeap
    
    Returns:
    The current largest element.
  - size
```
public int size()
```
    Description copied from interface: KNNHeap
    
    Current size of heap.
    
    Specified by:
    
    size in interface KNNHeap
    
    Returns:
    Heap size
  - isEmpty
```
public boolean isEmpty()
```
    Description copied from interface: KNNHeap
    
    Test if the heap is empty.
    
    Specified by:
    
    isEmpty in interface KNNHeap
    
    Returns:
    true when empty.
  - clear
```
public void clear()
```
    Description copied from interface: KNNHeap
    
    Clear the heap.
    
    Specified by:
    
    clear in interface KNNHeap
  - toKNNList
```
public DoubleIntegerDBIDKNNList toKNNList()
```
    Description copied from interface: KNNHeap
    
    Serialize to a KNNList. This empties the heap!
    
    Specified by:
    
    toKNNList in interface KNNHeap
    
    Returns:
    KNNList with the heaps contents.
  - peekDistance
```
protected double peekDistance()
```
    Peek the topmost distance.
    
    Returns:
    distance
  - peekInternalDBID
```
protected int peekInternalDBID()
```
    Peek the topmost internal ID.
    
    Returns:
    internal id

Class DoubleIntegerDBIDKNNHeap

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

k

heap

ties

numties

kdist

INITIAL_TIES_SIZE

Constructor Detail

DoubleIntegerDBIDKNNHeap

Method Detail

getK

getKNNDistance

insert

insert

updateHeap

addToTies

poll

pop

peek

size

isEmpty

clear

toKNNList

peekDistance

peekInternalDBID