Package elki.utilities.datastructures.heap

Class UpdatableHeap<O>

  • Type Parameters:
    O - object type
    public class UpdatableHeap<O>
extends Heap<O>
    A heap as used in OPTICS that allows updating entries.
    Since:
    0.4.0
    Author:
    Erich Schubert

    • Nested Class Summary

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected static int IN_TIES
      Constant for "in ties list", for tied heaps.
      protected it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap<java.lang.Object> index
      Holds the indices in the heap of each element.
      protected static int NO_VALUE
      Constant for "not in heap".

    • Constructor Summary

      Constructors 
      Constructor Description
      UpdatableHeap()
      Simple constructor with default size.
      UpdatableHeap​(int size)
      Constructor with predefined size.
      UpdatableHeap​(int size, java.util.Comparator<? super O> comparator)
      Constructor with predefined size and comparator.
      UpdatableHeap​(java.util.Comparator<? super O> comparator)
      Constructor with comparator.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(O e)
      Add an element to the heap.
      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, java.lang.Object cur)
      Execute a "Heapify Upwards" aka "SiftUp".
      protected void offerAt​(int pos, O e)
      Offer element at the given position.
      O poll()
      Remove the top element.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • NO_VALUE

        protected static final int NO_VALUE
        Constant for "not in heap".
        See Also:
        Constant Field Values

      • IN_TIES

        protected static final int IN_TIES
        Constant for "in ties list", for tied heaps.
        See Also:
        Constant Field Values

      • index

        protected final it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap<java.lang.Object> index
        Holds the indices in the heap of each element.

    • Constructor Detail

      • UpdatableHeap

        public UpdatableHeap()
        Simple constructor with default size.

      • UpdatableHeap

        public UpdatableHeap​(int size)
        Constructor with predefined size.
        Parameters:
        size - Size

      • UpdatableHeap

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

      • UpdatableHeap

        public UpdatableHeap​(int size,
                     java.util.Comparator<? super O> comparator)
        Constructor with predefined size and comparator.
        Parameters:
        size - Size
        comparator - Comparator

    • Method Detail

      • clear

        public void clear()
        Description copied from class: Heap
        Clear the heap.
        Overrides:
        clear in class Heap<O>

      • add

        public void add​(O e)
        Description copied from class: Heap
        Add an element to the heap.
        Overrides:
        add in class Heap<O>
        Parameters:
        e - Element to add

      • offerAt

        protected void offerAt​(int pos,
                       O e)
        Offer element at the given position.
        Parameters:
        pos - Position
        e - Element

      • poll

        public O poll()
        Description copied from class: Heap
        Remove the top element.
        Overrides:
        poll in class Heap<O>
        Returns:
        Top element.

      • heapifyUp

        protected void heapifyUp​(int pos,
                         java.lang.Object cur)
        Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.
        Overrides:
        heapifyUp in class Heap<O>
        Parameters:
        pos - insertion position
        cur - Element to insert

      • heapifyDown

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