Class IntegerObjectMaxHeap<V>

  • Type Parameters:
    V - Value type
    All Implemented Interfaces:
    IntegerObjectHeap<V>

    public class IntegerObjectMaxHeap<V>
    extends java.lang.Object
    implements IntegerObjectHeap<V>
    Binary heap for int 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 int[] 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​(int o, V v)
      Add a key-value pair to the heap
      void add​(int 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​(int 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​(int cur, java.lang.Object val)
      Invoke heapify-down for the root object.
      private void heapifyUp​(int twopos, int cur, java.lang.Object val)
      Heapify-Up method for 2-ary heap.
      boolean isEmpty()
      Is the heap empty?
      int peekKey()
      Get the current top key.
      V peekValue()
      Get the current top value.
      void poll()
      Remove the first element.
      void replaceTopElement​(int 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()  
      IntegerObjectMaxHeap.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 int[] 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

      • IntegerObjectMaxHeap

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

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

      • add

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

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

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

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

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