public class DoubleMaxHeap extends Object implements DoubleHeap
Modifier and Type | Class and Description |
---|---|
private class |
DoubleMaxHeap.UnsortedIter
Unsorted iterator - in heap order.
|
Modifier and Type | Field and 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.
|
Constructor and Description |
---|
DoubleMaxHeap()
Constructor, with default size.
|
DoubleMaxHeap(int minsize)
Constructor, with given minimum size.
|
Modifier and Type | Method and Description |
---|---|
void |
add(double o)
Add a key-value pair to the heap
|
void |
add(double key,
int max)
Add a key-value pair to the heap, except if the new element is larger than
the top, and we are at design size (overflow)
|
void |
clear()
Delete all elements from the heap.
|
private void |
heapifyDown(double cur)
Invoke heapify-down for the root object.
|
private void |
heapifyUp(int twopos,
double cur)
Heapify-Up method for 2-ary heap.
|
boolean |
isEmpty()
Is the heap empty?
|
double |
peek()
Get the current top key
|
double |
poll()
Remove the first element
|
double |
replaceTopElement(double reinsert)
Combined operation that removes the top element, and inserts a new element
instead.
|
int |
size()
Query the size
|
String |
toString() |
DoubleMaxHeap.UnsortedIter |
unsortedIter()
Get an unsorted iterator to inspect the heap.
|
protected double[] twoheap
protected int size
private static final int TWO_HEAP_INITIAL_SIZE
public DoubleMaxHeap()
public DoubleMaxHeap(int minsize)
minsize
- Minimum sizepublic void clear()
DoubleHeap
clear
in interface DoubleHeap
public int size()
DoubleHeap
size
in interface DoubleHeap
public boolean isEmpty()
DoubleHeap
isEmpty
in interface DoubleHeap
true
when the size is 0.public void add(double o)
DoubleHeap
add
in interface DoubleHeap
o
- Keypublic void add(double key, int max)
DoubleHeap
add
in interface DoubleHeap
key
- Keymax
- Maximum size of heappublic double replaceTopElement(double reinsert)
DoubleHeap
replaceTopElement
in interface DoubleHeap
reinsert
- New element to insertprivate void heapifyUp(int twopos, double cur)
twopos
- Position in 2-ary heap.cur
- Current objectpublic double poll()
DoubleHeap
poll
in interface DoubleHeap
private void heapifyDown(double cur)
cur
- Object to insert.public double peek()
DoubleHeap
peek
in interface DoubleHeap
public DoubleMaxHeap.UnsortedIter unsortedIter()
DoubleHeap
unsortedIter
in interface DoubleHeap
Copyright © 2015 ELKI Development Team, Lehr- und Forschungseinheit für Datenbanksysteme, Ludwig-Maximilians-Universität München. License information.