Class DoubleIntegerMinHeap

  • All Implemented Interfaces:
    DoubleIntegerHeap

    public class DoubleIntegerMinHeap
    extends java.lang.Object
    implements DoubleIntegerHeap
    Binary heap for double keys and int 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 int[] twovals
      Base heap values.
    • Method Summary

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

      • DoubleIntegerMinHeap

        public DoubleIntegerMinHeap()
        Constructor, with default size.
      • DoubleIntegerMinHeap

        public DoubleIntegerMinHeap​(int minsize)
        Constructor, with given minimum size.
        Parameters:
        minsize - Minimum size
    • Method Detail

      • add

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

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

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

        private void heapifyUp​(int twopos,
                               double cur,
                               int 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,
                                 int 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: DoubleIntegerHeap
        Contains operation for a key (slow: with a linear scan).
        Specified by:
        containsKey in interface DoubleIntegerHeap
        Parameters:
        q - Key
        Returns:
        true if the key is contained in the heap.
      • containsValue

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