DoubleObjectMaxHeap (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

java.lang.Object
- de.lmu.ifi.dbs.elki.utilities.datastructures.heap.DoubleObjectMaxHeap<V>

Type Parameters:
V - Value type

All Implemented Interfaces:

DoubleObjectHeap<V>
```
public class DoubleObjectMaxHeap<V>
extends Object
implements DoubleObjectHeap<V>
```
Advanced priority queue class, based on a binary heap (for small sizes), which will for larger heaps be accompanied by a 4-ary heap (attached below the root of the two-ary heap, making the root actually 3-ary). This code was automatically instantiated for the types: Double and Object This combination was found to work quite well in benchmarks, but YMMV. Some other observations from benchmarking:
- Bulk loading did not improve things
- Primitive heaps are substantially faster.
- Since an array in Java has an overhead of 12 bytes, odd-sized object and integer arrays are actually well aligned both for 2-ary and 4-ary heaps.
- Workload makes a huge difference. A load-once, poll-until-empty priority queue is something different than e.g. a top-k heap, which will see a lot of top element replacements.
- Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for top-k make a difference.
- Different day, different benchmark results ...

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

private class DoubleObjectMaxHeap.UnsortedIter
Unsorted iterator - in heap order.

Nested Classes
Modifier and Type	Class and Description
`private class`	`DoubleObjectMaxHeap.UnsortedIter` Unsorted iterator - in heap order.

Field Summary

Fields
Modifier and Type	Field and Description
`private static int`	`FOUR_HEAP_INITIAL_SIZE` Initial size of 4-ary heap when initialized. 21 = 4-ary heap of height 2: 1 + 4 + 44 85 = 4-ary heap of height 3: 21 + 444 341 = 4-ary heap of height 4: 85 + 4444 Since we last grew by 255 (to 511), let's use 341.
`protected double[]`	`fourheap` Extension heap.
`protected Object[]`	`fourvals` Extension heapvalues.
`protected int`	`modCount` (Structural) modification counter.
`protected int`	`size` Current size of heap.
`private static int`	`TWO_HEAP_INITIAL_SIZE` Initial size of the 2-ary heap.
`private static int`	`TWO_HEAP_MAX_SIZE` Maximum size of the 2-ary heap.
`protected double[]`	`twoheap` Base heap.
`protected Object[]`	`twovals` Base heap values.

Constructor Summary

Constructors
Constructor and Description

DoubleObjectMaxHeap()
Constructor, with default size.

DoubleObjectMaxHeap(int minsize)
Constructor, with given minimum size.

Constructors
Constructor and Description
`DoubleObjectMaxHeap()` Constructor, with default size.
`DoubleObjectMaxHeap(int minsize)` Constructor, with given minimum size.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`add(double o, V v)` Add a key-value pair to the heap
`void`	`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.
`private void`	`heapifyDown(double reinsert, Object val)` Invoke heapify-down for the root object.
`private void`	`heapifyDown2(int twopos, double cur, Object val)` Heapify-Down for 2-ary heap.
`private void`	`heapifyDown4(int fourpos, double cur, Object val)` Heapify-Down for 4-ary heap.
`private void`	`heapifyUp2(int twopos, double cur, Object val)` Heapify-Up method for 2-ary heap.
`private void`	`heapifyUp4(int fourpos, double cur, Object val)` Heapify-Up method for 4-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
`String`	`toString()`
`DoubleObjectMaxHeap.UnsortedIter`	`unsortedIter()` Get an unsorted iterator to inspect the heap.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - twoheap
```
protected double[] twoheap
```
    Base heap.
  - twovals
```
protected Object[] twovals
```
    Base heap values.
  - fourheap
```
protected double[] fourheap
```
    Extension heap.
  - fourvals
```
protected Object[] fourvals
```
    Extension heapvalues.
  - size
```
protected int size
```
    Current size of heap.
  - modCount
```
protected int modCount
```
    (Structural) modification counter. Used to invalidate iterators.
  - TWO_HEAP_MAX_SIZE
```
private static final int TWO_HEAP_MAX_SIZE
```
    Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements.
    
    See Also:
    Constant Field Values
  - TWO_HEAP_INITIAL_SIZE
```
private static final int TWO_HEAP_INITIAL_SIZE
```
    Initial size of the 2-ary heap.
    
    See Also:
    Constant Field Values
  - FOUR_HEAP_INITIAL_SIZE
```
private static final int FOUR_HEAP_INITIAL_SIZE
```
    Initial size of 4-ary heap when initialized. 21 = 4-ary heap of height 2: 1 + 4 + 4*4 85 = 4-ary heap of height 3: 21 + 4*4*4 341 = 4-ary heap of height 4: 85 + 4*4*4*4 Since we last grew by 255 (to 511), let's use 341.
    
    See Also:
    Constant Field Values
- Constructor Detail
  - DoubleObjectMaxHeap
```
public DoubleObjectMaxHeap()
```
    Constructor, with default size.
  - DoubleObjectMaxHeap
```
public DoubleObjectMaxHeap(int minsize)
```
    Constructor, with given minimum size.
    
    Parameters:
    minsize - Minimum size
- Method Detail
  - clear
```
public void clear()
```
    Description copied from interface: DoubleObjectHeap
    
    Clear the heap contents.
    
    Specified by:
    
    clear in interface DoubleObjectHeap<V>
  - size
```
public int size()
```
    Description copied from interface: DoubleObjectHeap
    
    Query the size
    
    Specified by:
    
    size in interface DoubleObjectHeap<V>
    
    Returns:
    Size
  - isEmpty
```
public boolean isEmpty()
```
    Description copied from interface: DoubleObjectHeap
    
    Is the heap empty?
    
    Specified by:
    
    isEmpty in interface DoubleObjectHeap<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 interface DoubleObjectHeap<V>
    
    Parameters:
    o - Key
    v - 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 interface DoubleObjectHeap<V>
    
    Parameters:
    key - Key
    val - Value
    max - 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 interface DoubleObjectHeap<V>
    
    Parameters:
    reinsert - Key of new element
    val - Value of new element
  - heapifyUp2
```
private void heapifyUp2(int twopos,
              double cur,
              Object val)
```
    Heapify-Up method for 2-ary heap.
    
    Parameters:
    twopos - Position in 2-ary heap.
    cur - Current object
    val - Current value
  - heapifyUp4
```
private void heapifyUp4(int fourpos,
              double cur,
              Object val)
```
    Heapify-Up method for 4-ary heap.
    
    Parameters:
    fourpos - Position in 4-ary heap.
    cur - Current object
    val - Current value
  - poll
```
public void poll()
```
    Description copied from interface: DoubleObjectHeap
    
    Remove the first element
    
    Specified by:
    
    poll in interface DoubleObjectHeap<V>
  - heapifyDown
```
private void heapifyDown(double reinsert,
               Object val)
```
    Invoke heapify-down for the root object.
    
    Parameters:
    reinsert - Object to insert.
    val - Value to reinsert.
  - heapifyDown2
```
private void heapifyDown2(int twopos,
                double cur,
                Object val)
```
    Heapify-Down for 2-ary heap.
    
    Parameters:
    twopos - Position in 2-ary heap.
    cur - Current object
    val - Value to reinsert.
  - heapifyDown4
```
private void heapifyDown4(int fourpos,
                double cur,
                Object val)
```
    Heapify-Down for 4-ary heap.
    
    Parameters:
    fourpos - Position in 4-ary heap.
    cur - Current object
    val - Value to reinsert.
  - peekKey
```
public double peekKey()
```
    Description copied from interface: DoubleObjectHeap
    
    Get the current top key
    
    Specified by:
    
    peekKey in interface DoubleObjectHeap<V>
    
    Returns:
    Top key
  - peekValue
```
public V peekValue()
```
    Description copied from interface: DoubleObjectHeap
    
    Get the current top value
    
    Specified by:
    
    peekValue in interface DoubleObjectHeap<V>
    
    Returns:
    Value
  - toString
```
public String toString()
```
    Overrides:
    
    toString in class Object
  - unsortedIter
```
public DoubleObjectMaxHeap.UnsortedIter unsortedIter()
```
    Description copied from interface: DoubleObjectHeap
    
    Get an unsorted iterator to inspect the heap.
    
    Specified by:
    
    unsortedIter in interface DoubleObjectHeap<V>
    
    Returns:
    Iterator

Class DoubleObjectMaxHeap<V>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

twoheap

twovals

fourheap

fourvals

size

modCount

TWO_HEAP_MAX_SIZE

TWO_HEAP_INITIAL_SIZE

FOUR_HEAP_INITIAL_SIZE

Constructor Detail

DoubleObjectMaxHeap

DoubleObjectMaxHeap

Method Detail

clear

size

isEmpty

add

add

replaceTopElement

heapifyUp2

heapifyUp4

poll

heapifyDown

heapifyDown2

heapifyDown4

peekKey

peekValue

toString

unsortedIter