Package elki.utilities.datastructures.heap

Class DoubleLongMinHeap

  • All Implemented Interfaces:
    DoubleLongHeap
    public class DoubleLongMinHeap
extends java.lang.Object
implements DoubleLongHeap
    Binary heap for double keys and long values.

    This class is generated from a template.

    Since:
    0.6.0
    Author:
    Erich Schubert

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private class  DoubleLongMinHeap.UnsortedIter
      Unsorted iterator - in heap order.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected int size
      Current size of heap.
      private static int TWO_HEAP_INITIAL_SIZE
      Initial size of the 2-ary heap.
      protected double[] twoheap
      Base heap.
      protected long[] twovals
      Base heap values.

    • Constructor Summary

      Constructors 
      Constructor Description
      DoubleLongMinHeap()
      Constructor, with default size.
      DoubleLongMinHeap​(int minsize)
      Constructor, with given minimum size.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(double o, long v)
      Add a key-value pair to the heap
      void add​(double key, long val, int max)
      Add a key-value pair to the heap if it improves the top.
      void clear()
      Clear the heap contents.
      boolean containsKey​(double q)
      Contains operation for a key (slow: with a linear scan).
      boolean containsValue​(long q)
      Contains operation for a value (slow: with a linear scan).
      private void heapifyDown​(double cur, long val)
      Invoke heapify-down for the root object.
      private void heapifyUp​(int twopos, double cur, long val)
      Heapify-Up method for 2-ary heap.
      boolean isEmpty()
      Is the heap empty?
      double peekKey()
      Get the current top key.
      long peekValue()
      Get the current top value.
      void poll()
      Remove the first element.
      void replaceTopElement​(double reinsert, long val)
      Combined operation that removes the top element, and inserts a new element instead.
      int size()
      Query the size.
      java.lang.String toString()  
      DoubleLongMinHeap.UnsortedIter unsortedIter()
      Get an unsorted iterator to inspect the heap.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • twoheap

        protected double[] twoheap
        Base heap.

      • twovals

        protected long[] twovals
        Base heap values.

      • size

        protected int size
        Current size of heap.

      • TWO_HEAP_INITIAL_SIZE

        private static final int TWO_HEAP_INITIAL_SIZE
        Initial size of the 2-ary heap.
        See Also:
        Constant Field Values

    • Constructor Detail

      • DoubleLongMinHeap

        public DoubleLongMinHeap()
        Constructor, with default size.

      • DoubleLongMinHeap

        public DoubleLongMinHeap​(int minsize)
        Constructor, with given minimum size.
        Parameters:
        minsize - Minimum size

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Description copied from interface: DoubleLongHeap
        Is the heap empty?
        Specified by:
        isEmpty in interface DoubleLongHeap
        Returns:
        true when the size is 0.

      • add

        public void add​(double o,
                long v)
        Description copied from interface: DoubleLongHeap
        Add a key-value pair to the heap
        Specified by:
        add in interface DoubleLongHeap
        Parameters:
        o - Key
        v - Value

      • add

        public void add​(double key,
                long val,
                int max)
        Description copied from interface: DoubleLongHeap
        Add a key-value pair to the heap if it improves the top.
        Specified by:
        add in interface DoubleLongHeap
        Parameters:
        key - Key
        val - Value
        max - Desired maximum size

      • replaceTopElement

        public void replaceTopElement​(double reinsert,
                              long val)
        Description copied from interface: DoubleLongHeap
        Combined operation that removes the top element, and inserts a new element instead.
        Specified by:
        replaceTopElement in interface DoubleLongHeap
        Parameters:
        reinsert - Key of new element
        val - Value of new element

      • heapifyUp

        private void heapifyUp​(int twopos,
                       double cur,
                       long val)
        Heapify-Up method for 2-ary heap.
        Parameters:
        twopos - Position in 2-ary heap.
        cur - Current object
        val - Current value

      • heapifyDown

        private void heapifyDown​(double cur,
                         long val)
        Invoke heapify-down for the root object.
        Parameters:
        cur - Object to insert.
        val - Value to reinsert.

      • peekKey

        public double peekKey()
        Description copied from interface: DoubleLongHeap
        Get the current top key.
        Specified by:
        peekKey in interface DoubleLongHeap
        Returns:
        Top key

      • containsKey

        public boolean containsKey​(double q)
        Description copied from interface: DoubleLongHeap
        Contains operation for a key (slow: with a linear scan).
        Specified by:
        containsKey in interface DoubleLongHeap
        Parameters:
        q - Key
        Returns:
        true if the key is contained in the heap.

      • containsValue

        public boolean containsValue​(long q)
        Description copied from interface: DoubleLongHeap
        Contains operation for a value (slow: with a linear scan).
        Specified by:
        containsValue in interface DoubleLongHeap
        Parameters:
        q - Value
        Returns:
        true if the value is contained in the heap.

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object