Package smile.sort

Class HeapSelect<T extends Comparable<? super T>>

java.lang.Object
smile.sort.HeapSelect<T>
Type Parameters:
T - the data type of stream elements.
public class HeapSelect<T extends Comparable<? super T>> extends Object
This class tracks the smallest values seen thus far in a stream of values. This implements a single-pass selection for large data sets. That is, we have a stream of input values, each of which we get to see only once. We want to be able to report at any time, say after n values, the i-th smallest value see so far.

  • Constructor Summary

    Constructors
    Constructor
    Description
    HeapSelect(Class<?> clazz, int k)
    Constructor.
    HeapSelect(T[] heap)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(T datum)
    Assimilate a new value from the stream.
    T
    get(int i)
    Returns the i-th smallest value seen so far.
    void
    heapify()
    In case of avoiding creating new objects frequently, one may check and update the peek object directly and call this method to sort the internal array in heap order.
    T
    peek()
    Returns the k-th smallest value seen so far.
    int
    size()
    Returns the number of objects that have been added into heap.
    void
    sort()
    Sort the smallest values.
    T[]
    toArray()
    Returns the array back the heap.
    T[]
    toArray(T[] a)
    Returns the array back the heap.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • HeapSelect

      public HeapSelect(Class<?> clazz, int k)
      Constructor.
      Parameters:
      clazz - the data type of elements.
      k - the size of heap.

    • HeapSelect

      public HeapSelect(T[] heap)
      Constructor.
      Parameters:
      heap - the array to store smallest values to track.

  • Method Details

    • size

      public int size()
      Returns the number of objects that have been added into heap.
      Returns:
      the number of objects that have been added into heap.

    • toArray

      public T[] toArray()
      Returns the array back the heap.
      Returns:
      the array back the heap.

    • toArray

      public T[] toArray(T[] a)
      Returns the array back the heap.
      Parameters:
      a - the array to copy into.
      Returns:
      the array back the heap.

    • add

      public void add(T datum)
      Assimilate a new value from the stream.
      Parameters:
      datum - a new value.

    • heapify

      public void heapify()
      In case of avoiding creating new objects frequently, one may check and update the peek object directly and call this method to sort the internal array in heap order.

    • peek

      public T peek()
      Returns the k-th smallest value seen so far.
      Returns:
      the k-th smallest value.

    • get

      public T get(int i)
      Returns the i-th smallest value seen so far. i = 0 returns the smallest value seen, i = 1 the second largest, ..., i = k-1 the last position tracked. Also, i must be less than the number of previous assimilated.
      Parameters:
      i - the ordinal index of smallest values.
      Returns:
      the i-th smallest value.

    • sort

      public void sort()
      Sort the smallest values.