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