Package elki.utilities.datastructures.heap

Class ComparableMinHeap<K extends java.lang.Comparable<? super K>>

  • Type Parameters:
    K - Key type
    All Implemented Interfaces:
    ObjectHeap<K>
    public class ComparableMinHeap<K extends java.lang.Comparable<? super K>>
extends java.lang.Object
implements ObjectHeap<K>
    Binary heap for primitive types.

    This class is generated from a template.

    Since:
    0.5.5
    Author:
    Erich Schubert

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private class  ComparableMinHeap.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 java.lang.Comparable<java.lang.Object>[] twoheap
      Base heap.

    • Constructor Summary

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

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(K o)
      Add a key-value pair to the heap
      void add​(K key, int max)
      Add a key-value pair to the heap, except if the new element is larger than the top, and we are at design size (overflow)
      void clear()
      Delete all elements from the heap.
      private void heapifyDown​(java.lang.Comparable<java.lang.Object> cur)
      Invoke heapify-down for the root object.
      private void heapifyUp​(int twopos, java.lang.Comparable<java.lang.Object> cur)
      Heapify-Up method for 2-ary heap.
      boolean isEmpty()
      Is the heap empty?
      K peek()
      Get the current top key
      K poll()
      Remove the first element
      K replaceTopElement​(K reinsert)
      Combined operation that removes the top element, and inserts a new element instead.
      int size()
      Query the size
      java.lang.String toString()  
      ComparableMinHeap.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 java.lang.Comparable<java.lang.Object>[] twoheap
        Base heap.

      • 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

      • ComparableMinHeap

        public ComparableMinHeap()
        Constructor, with default size.

      • ComparableMinHeap

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

    • Method Detail

      • clear

        public void clear()
        Description copied from interface: ObjectHeap
        Delete all elements from the heap.
        Specified by:
        clear in interface ObjectHeap<K extends java.lang.Comparable<? super K>>

      • size

        public int size()
        Description copied from interface: ObjectHeap
        Query the size
        Specified by:
        size in interface ObjectHeap<K extends java.lang.Comparable<? super K>>
        Returns:
        Size

      • isEmpty

        public boolean isEmpty()
        Description copied from interface: ObjectHeap
        Is the heap empty?
        Specified by:
        isEmpty in interface ObjectHeap<K extends java.lang.Comparable<? super K>>
        Returns:
        true when the size is 0.

      • add

        public void add​(K o)
        Description copied from interface: ObjectHeap
        Add a key-value pair to the heap
        Specified by:
        add in interface ObjectHeap<K extends java.lang.Comparable<? super K>>
        Parameters:
        o - Key

      • add

        public void add​(K key,
                int max)
        Description copied from interface: ObjectHeap
        Add a key-value pair to the heap, except if the new element is larger than the top, and we are at design size (overflow)
        Specified by:
        add in interface ObjectHeap<K extends java.lang.Comparable<? super K>>
        Parameters:
        key - Key
        max - Maximum size of heap

      • replaceTopElement

        public K replaceTopElement​(K reinsert)
        Description copied from interface: ObjectHeap
        Combined operation that removes the top element, and inserts a new element instead.
        Specified by:
        replaceTopElement in interface ObjectHeap<K extends java.lang.Comparable<? super K>>
        Parameters:
        reinsert - New element to insert
        Returns:
        Previous top element of the heap

      • heapifyUp

        private void heapifyUp​(int twopos,
                       java.lang.Comparable<java.lang.Object> cur)
        Heapify-Up method for 2-ary heap.
        Parameters:
        twopos - Position in 2-ary heap.
        cur - Current object

      • poll

        public K poll()
        Description copied from interface: ObjectHeap
        Remove the first element
        Specified by:
        poll in interface ObjectHeap<K extends java.lang.Comparable<? super K>>
        Returns:
        Top element

      • heapifyDown

        private void heapifyDown​(java.lang.Comparable<java.lang.Object> cur)
        Invoke heapify-down for the root object.
        Parameters:
        cur - Object to insert.

      • peek

        public K peek()
        Description copied from interface: ObjectHeap
        Get the current top key
        Specified by:
        peek in interface ObjectHeap<K extends java.lang.Comparable<? super K>>
        Returns:
        Top key

      • toString

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