Package elki.utilities.datastructures.heap

Class Heap<E>

  • Type Parameters:
    E - Element type. Should be Comparable or a Comparator needs to be given.
    Direct Known Subclasses:
    UpdatableHeap
    public class Heap<E>
extends java.lang.Object
    Basic in-memory heap structure. Similar to a PriorityQueue, but with some additional operations.

    Additionally, this heap is built lazily: if you first add many elements, then poll the heap, it will be bulk-loaded in O(n) instead of iteratively built in O(n log n). This is implemented via a simple validTo counter.

    Since:
    0.4.0
    Author:
    Erich Schubert

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  Heap.UnorderedIter
      Heap iterator.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.util.Comparator<java.lang.Object> comparator
      The comparator.
      private static int DEFAULT_INITIAL_CAPACITY
      Default initial capacity.
      private int modCount
      (Structural) modification counter.
      protected java.lang.Object[] queue
      Heap storage.
      protected int size
      Current number of objects.

    • Constructor Summary

      Constructors 
      Constructor Description
      Heap()
      Default constructor: default capacity, natural ordering.
      Heap​(int size)
      Constructor with initial capacity, natural ordering.
      Heap​(int size, java.util.Comparator<? super E> comparator)
      Constructor with initial capacity and Comparator.
      Heap​(java.util.Comparator<? super E> comparator)
      Constructor with Comparator.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(E e)
      Add an element to the heap.
      void add​(E e, int maxsize)
      Add an element to the heap.
      protected java.lang.String checkHeap()
      Test whether the heap is still valid.
      void clear()
      Clear the heap.
      protected boolean heapifyDown​(int ipos, java.lang.Object cur)
      Execute a "Heapify Downwards" aka "SiftDown".
      protected void heapifyUp​(int pos, E elem)
      Execute a "Heapify Upwards" aka "SiftUp".
      protected void heapModified()
      Called at the end of each heap modification.
      boolean isEmpty()
      Test for emptiness.
      E peek()
      Peek at the top element.
      E poll()
      Remove the top element.
      int size()
      Get the heap size.
      Heap.UnorderedIter unorderedIter()
      Get an unordered heap iterator.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • queue

        protected java.lang.Object[] queue
        Heap storage.

      • size

        protected int size
        Current number of objects.

      • comparator

        protected final java.util.Comparator<java.lang.Object> comparator
        The comparator.

      • modCount

        private int modCount
        (Structural) modification counter. Used to invalidate iterators.

      • DEFAULT_INITIAL_CAPACITY

        private static final int DEFAULT_INITIAL_CAPACITY
        Default initial capacity.
        See Also:
        Constant Field Values

    • Constructor Detail

      • Heap

        public Heap()
        Default constructor: default capacity, natural ordering.

      • Heap

        public Heap​(int size)
        Constructor with initial capacity, natural ordering.
        Parameters:
        size - initial size

      • Heap

        public Heap​(java.util.Comparator<? super E> comparator)
        Constructor with Comparator.
        Parameters:
        comparator - Comparator

      • Heap

        public Heap​(int size,
            java.util.Comparator<? super E> comparator)
        Constructor with initial capacity and Comparator.
        Parameters:
        size - initial capacity
        comparator - Comparator

    • Method Detail

      • add

        public void add​(E e)
        Add an element to the heap.
        Parameters:
        e - Element to add

      • add

        public void add​(E e,
                int maxsize)
        Add an element to the heap.
        Parameters:
        e - Element to add
        maxsize - Maximum size

      • peek

        public E peek()
        Peek at the top element.
        Returns:
        Top element.

      • poll

        public E poll()
        Remove the top element.
        Returns:
        Top element.

      • heapifyUp

        protected void heapifyUp​(int pos,
                         E elem)
        Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.
        Parameters:
        pos - insertion position
        elem - Element to insert

      • heapifyDown

        protected boolean heapifyDown​(int ipos,
                              java.lang.Object cur)
        Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.
        Parameters:
        ipos - re-insertion position
        cur - Object to reinsert
        Returns:
        true when the order was changed

      • size

        public int size()
        Get the heap size.
        Returns:
        Heap size

      • isEmpty

        public boolean isEmpty()
        Test for emptiness.
        Returns:
        true when the heap is empty

      • clear

        public void clear()
        Clear the heap.

      • heapModified

        protected void heapModified()
        Called at the end of each heap modification.

      • unorderedIter

        public Heap.UnorderedIter unorderedIter()
        Get an unordered heap iterator.
        Returns:
        Iterator.

      • checkHeap

        protected java.lang.String checkHeap()
        Test whether the heap is still valid.

        Debug method.

        Returns:
        null when the heap is correct