Class ComparatorMaxHeap<K>
- java.lang.Object
-
- elki.utilities.datastructures.heap.ComparatorMaxHeap<K>
-
- Type Parameters:
K
- Key type
- All Implemented Interfaces:
ObjectHeap<K>
public class ComparatorMaxHeap<K> extends java.lang.Object implements ObjectHeap<K>
Binary heap for primitive types.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
ComparatorMaxHeap.UnsortedIter
Unsorted iterator - in heap order.
-
Field Summary
Fields Modifier and Type Field Description protected java.util.Comparator<java.lang.Object>
comparator
Comparatorprotected int
size
Current size of heap.private static int
TWO_HEAP_INITIAL_SIZE
Initial size of the 2-ary heap.protected java.lang.Object[]
twoheap
Base heap.
-
Constructor Summary
Constructors Constructor Description ComparatorMaxHeap(int minsize, java.util.Comparator<? super K> comparator)
Constructor, with given minimum size.ComparatorMaxHeap(java.util.Comparator<? super K> comparator)
Constructor, with default size.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(K o)
Add a key-value pair to the heapvoid
add(K 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(java.lang.Object cur)
Invoke heapify-down for the root object.private void
heapifyUp(int twopos, java.lang.Object cur)
Heapify-Up method for 2-ary heap.boolean
isEmpty()
Is the heap empty?K
peek()
Get the current top keyK
poll()
Remove the first elementK
replaceTopElement(K reinsert)
Combined operation that removes the top element, and inserts a new element instead.int
size()
Query the sizejava.lang.String
toString()
ComparatorMaxHeap.UnsortedIter
unsortedIter()
Get an unsorted iterator to inspect the heap.
-
-
-
Field Detail
-
twoheap
protected java.lang.Object[] twoheap
Base heap.
-
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
-
comparator
protected java.util.Comparator<java.lang.Object> comparator
Comparator
-
-
Constructor Detail
-
ComparatorMaxHeap
public ComparatorMaxHeap(java.util.Comparator<? super K> comparator)
Constructor, with default size.- Parameters:
comparator
- Comparator
-
ComparatorMaxHeap
public ComparatorMaxHeap(int minsize, java.util.Comparator<? super K> comparator)
Constructor, with given minimum size.- Parameters:
minsize
- Minimum sizecomparator
- Comparator
-
-
Method Detail
-
clear
public void clear()
Description copied from interface:ObjectHeap
Delete all elements from the heap.- Specified by:
clear
in interfaceObjectHeap<K>
-
size
public int size()
Description copied from interface:ObjectHeap
Query the size- Specified by:
size
in interfaceObjectHeap<K>
- Returns:
- Size
-
isEmpty
public boolean isEmpty()
Description copied from interface:ObjectHeap
Is the heap empty?- Specified by:
isEmpty
in interfaceObjectHeap<K>
- Returns:
true
when the size is 0.
-
add
public void add(K o)
Description copied from interface:ObjectHeap
Add a key-value pair to the heap- Specified by:
add
in interfaceObjectHeap<K>
- Parameters:
o
- Key
-
add
public void add(K key, int max)
Description copied from interface:ObjectHeap
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)- Specified by:
add
in interfaceObjectHeap<K>
- Parameters:
key
- Keymax
- Maximum size of heap
-
replaceTopElement
public K replaceTopElement(K reinsert)
Description copied from interface:ObjectHeap
Combined operation that removes the top element, and inserts a new element instead.- Specified by:
replaceTopElement
in interfaceObjectHeap<K>
- Parameters:
reinsert
- New element to insert- Returns:
- Previous top element of the heap
-
heapifyUp
private void heapifyUp(int twopos, java.lang.Object cur)
Heapify-Up method for 2-ary heap.- Parameters:
twopos
- Position in 2-ary heap.cur
- Current object
-
poll
public K poll()
Description copied from interface:ObjectHeap
Remove the first element- Specified by:
poll
in interfaceObjectHeap<K>
- Returns:
- Top element
-
heapifyDown
private void heapifyDown(java.lang.Object cur)
Invoke heapify-down for the root object.- Parameters:
cur
- Object to insert.
-
peek
public K peek()
Description copied from interface:ObjectHeap
Get the current top key- Specified by:
peek
in interfaceObjectHeap<K>
- Returns:
- Top key
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
unsortedIter
public ComparatorMaxHeap.UnsortedIter unsortedIter()
Description copied from interface:ObjectHeap
Get an unsorted iterator to inspect the heap.- Specified by:
unsortedIter
in interfaceObjectHeap<K>
- Returns:
- Iterator
-
-