Class UpdatableHeap<O>
- java.lang.Object
-
- elki.utilities.datastructures.heap.Heap<O>
-
- elki.utilities.datastructures.heap.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
-
Nested classes/interfaces inherited from class elki.utilities.datastructures.heap.Heap
Heap.UnorderedIter
-
-
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".-
Fields inherited from class elki.utilities.datastructures.heap.Heap
comparator, queue, size
-
-
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 elki.utilities.datastructures.heap.Heap
add, checkHeap, heapModified, isEmpty, peek, size, unorderedIter
-
-
-
-
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
- Sizecomparator
- Comparator
-
-
Method Detail
-
clear
public void clear()
Description copied from class:Heap
Clear the heap.
-
offerAt
protected void offerAt(int pos, O e)
Offer element at the given position.- Parameters:
pos
- Positione
- Element
-
heapifyUp
protected void heapifyUp(int pos, java.lang.Object cur)
Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.
-
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 classHeap<O>
- Parameters:
ipos
- re-insertion positioncur
- Object to reinsert- Returns:
- true when the order was changed
-
-