Package smile.sort

Class IntHeapSelect


  • public class IntHeapSelect
    extends java.lang.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.
    Author:
    Haifeng Li
    • Constructor Summary

      Constructors 
      Constructor Description
      IntHeapSelect​(int k)
      Constructor.
      IntHeapSelect​(int[] heap)
      Constructor.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      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.
      void sort()
      Sort the smallest values.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • IntHeapSelect

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

        public IntHeapSelect​(int[] heap)
        Constructor.
        Parameters:
        heap - the array to store smallest values to track.
    • Method Detail

      • add

        public void add​(int datum)
        Assimilate a new value from the stream.
      • peek

        public int peek()
        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.
      • sort

        public void sort()
        Sort the smallest values.