Class DoubleObjectMaxHeap<V>
- java.lang.Object
-
- elki.utilities.datastructures.heap.DoubleObjectMaxHeap<V>
-
- Type Parameters:
V
- Value type
- All Implemented Interfaces:
DoubleObjectHeap<V>
public class DoubleObjectMaxHeap<V> extends java.lang.Object implements DoubleObjectHeap<V>
Binary heap for double keys and Object values.This class is generated from a template.
- Since:
- 0.6.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
DoubleObjectMaxHeap.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 double[]
twoheap
Base heap.protected java.lang.Object[]
twovals
Base heap values.
-
Constructor Summary
Constructors Constructor Description DoubleObjectMaxHeap()
Constructor, with default size.DoubleObjectMaxHeap(int minsize)
Constructor, with given minimum size.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(double o, V v)
Add a key-value pair to the heapvoid
add(double 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(double 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(double cur, java.lang.Object val)
Invoke heapify-down for the root object.private void
heapifyUp(int twopos, double cur, java.lang.Object val)
Heapify-Up method for 2-ary heap.boolean
isEmpty()
Is the heap empty?double
peekKey()
Get the current top key.V
peekValue()
Get the current top value.void
poll()
Remove the first element.void
replaceTopElement(double 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()
DoubleObjectMaxHeap.UnsortedIter
unsortedIter()
Get an unsorted iterator to inspect the heap.
-
-
-
Field Detail
-
twoheap
protected double[] 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
-
-
Method Detail
-
clear
public void clear()
Description copied from interface:DoubleObjectHeap
Clear the heap contents.- Specified by:
clear
in interfaceDoubleObjectHeap<V>
-
size
public int size()
Description copied from interface:DoubleObjectHeap
Query the size.- Specified by:
size
in interfaceDoubleObjectHeap<V>
- Returns:
- Size
-
isEmpty
public boolean isEmpty()
Description copied from interface:DoubleObjectHeap
Is the heap empty?- Specified by:
isEmpty
in interfaceDoubleObjectHeap<V>
- Returns:
true
when the size is 0.
-
add
public void add(double o, V v)
Description copied from interface:DoubleObjectHeap
Add a key-value pair to the heap- Specified by:
add
in interfaceDoubleObjectHeap<V>
- Parameters:
o
- Keyv
- Value
-
add
public void add(double key, V val, int max)
Description copied from interface:DoubleObjectHeap
Add a key-value pair to the heap if it improves the top.- Specified by:
add
in interfaceDoubleObjectHeap<V>
- Parameters:
key
- Keyval
- Valuemax
- Desired maximum size
-
replaceTopElement
public void replaceTopElement(double reinsert, V val)
Description copied from interface:DoubleObjectHeap
Combined operation that removes the top element, and inserts a new element instead.- Specified by:
replaceTopElement
in interfaceDoubleObjectHeap<V>
- Parameters:
reinsert
- Key of new elementval
- Value of new element
-
heapifyUp
private void heapifyUp(int twopos, double cur, java.lang.Object val)
Heapify-Up method for 2-ary heap.- Parameters:
twopos
- Position in 2-ary heap.cur
- Current objectval
- Current value
-
poll
public void poll()
Description copied from interface:DoubleObjectHeap
Remove the first element.- Specified by:
poll
in interfaceDoubleObjectHeap<V>
-
heapifyDown
private void heapifyDown(double cur, java.lang.Object val)
Invoke heapify-down for the root object.- Parameters:
cur
- Object to insert.val
- Value to reinsert.
-
peekKey
public double peekKey()
Description copied from interface:DoubleObjectHeap
Get the current top key.- Specified by:
peekKey
in interfaceDoubleObjectHeap<V>
- Returns:
- Top key
-
peekValue
public V peekValue()
Description copied from interface:DoubleObjectHeap
Get the current top value.- Specified by:
peekValue
in interfaceDoubleObjectHeap<V>
- Returns:
- Value
-
containsKey
public boolean containsKey(double q)
Description copied from interface:DoubleObjectHeap
Contains operation for a key (slow: with a linear scan).- Specified by:
containsKey
in interfaceDoubleObjectHeap<V>
- Parameters:
q
- Key- Returns:
true
if the key is contained in the heap.
-
containsValue
public boolean containsValue(V q)
Description copied from interface:DoubleObjectHeap
Contains operation for a value (slow: with a linear scan).- Specified by:
containsValue
in interfaceDoubleObjectHeap<V>
- Parameters:
q
- Value- Returns:
true
if the value is contained in the heap.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
unsortedIter
public DoubleObjectMaxHeap.UnsortedIter unsortedIter()
Description copied from interface:DoubleObjectHeap
Get an unsorted iterator to inspect the heap.- Specified by:
unsortedIter
in interfaceDoubleObjectHeap<V>
- Returns:
- Iterator
-
-