Package elki.utilities.datastructures.heap

Class DoubleObjectMinHeap<V>

  • Type Parameters:
    V - Value type
    All Implemented Interfaces:
    DoubleObjectHeap<V>
    public class DoubleObjectMinHeap<V>
extends java.lang.Object
implements DoubleObjectHeap<V>
    Binary heap for double keys and Object values.

    This class is generated from a template.

    Since:
    0.6.0
    Author:
    Erich Schubert

    • 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 java.lang.Object[] twovals
      Base heap values.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(double o, V v)
      Add a key-value pair to the heap
      void add​(double key, V 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​(V q)
      Contains operation for a value (slow: with a linear scan).
      private void heapifyDown​(double cur, java.lang.Object val)
      Invoke heapify-down for the root object.
      private void heapifyUp​(int twopos, double cur, java.lang.Object val)
      Heapify-Up method for 2-ary heap.
      boolean isEmpty()
      Is the heap empty?
      double peekKey()
      Get the current top key.
      V peekValue()
      Get the current top value.
      void poll()
      Remove the first element.
      void replaceTopElement​(double reinsert, V val)
      Combined operation that removes the top element, and inserts a new element instead.
      int size()
      Query the size.
      java.lang.String toString()  
      DoubleObjectMinHeap.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 java.lang.Object[] 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

      • DoubleObjectMinHeap

        public DoubleObjectMinHeap()
        Constructor, with default size.

      • DoubleObjectMinHeap

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

    • Method Detail

      • add

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

      • add

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

      • replaceTopElement

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

      • heapifyUp

        private void heapifyUp​(int twopos,
                       double cur,
                       java.lang.Object 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,
                         java.lang.Object val)
        Invoke heapify-down for the root object.
        Parameters:
        cur - Object to insert.
        val - Value to reinsert.

      • containsKey

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

      • containsValue

        public boolean containsValue​(V q)
        Description copied from interface: DoubleObjectHeap
        Contains operation for a value (slow: with a linear scan).
        Specified by:
        containsValue in interface DoubleObjectHeap<V>
        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