Class IntHeapSelect

java.lang.Object
smile.sort.IntHeapSelect
public class IntHeapSelect 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
    IntHeapSelect(int k)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(int datum)
    Assimilate a new value from the stream.
    int
    get(int i)
    Returns the i-th smallest value seen so far.
    int
    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.
    int[]
    toArray()
    Returns a copy of the tracked smallest values in heap (unsorted) order.

    Methods inherited from class Object

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

  • Constructor Details

    • IntHeapSelect

      public IntHeapSelect(int k)
      Constructor.
      Parameters:
      k - the heap size.

  • Method Details

    • add

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

    • 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 int[] toArray()
      Returns a copy of the tracked smallest values in heap (unsorted) order. The length of the returned array is min(k, n).
      Returns:
      the tracked values.

    • peek

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

    • get

      public int 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.