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

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

Type Parameters:
V - Value type

All Implemented Interfaces:

IntegerObjectHeap<V>
```
public class IntegerObjectMinHeap<V>
extends Object
implements IntegerObjectHeap<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: Integer 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 IntegerObjectMinHeap.UnsortedIter
Unsorted iterator - in heap order.

Nested Classes
Modifier and Type	Class and Description
`private class`	`IntegerObjectMinHeap.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 int[]`	`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 int[]`	`twoheap` Base heap.
`protected Object[]`	`twovals` Base heap values.

Constructor Summary

Constructors
Constructor and Description

IntegerObjectMinHeap()
Constructor, with default size.

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

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

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`add(int o, V v)` Add a key-value pair to the heap
`void`	`add(int 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(int reinsert, Object val)` Invoke heapify-down for the root object.
`private void`	`heapifyDown2(int twopos, int cur, Object val)` Heapify-Down for 2-ary heap.
`private void`	`heapifyDown4(int fourpos, int cur, Object val)` Heapify-Down for 4-ary heap.
`private void`	`heapifyUp2(int twopos, int cur, Object val)` Heapify-Up method for 2-ary heap.
`private void`	`heapifyUp4(int fourpos, int cur, Object val)` Heapify-Up method for 4-ary heap.
`boolean`	`isEmpty()` Is the heap empty?
`int`	`peekKey()` Get the current top key
`V`	`peekValue()` Get the current top value
`void`	`poll()` Remove the first element
`void`	`replaceTopElement(int reinsert, V val)` Combined operation that removes the top element, and inserts a new element instead.
`int`	`size()` Query the size
`String`	`toString()`
`IntegerObjectMinHeap.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 int[] twoheap
```
    Base heap.
  - twovals
```
protected Object[] twovals
```
    Base heap values.
  - fourheap
```
protected int[] 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
  - IntegerObjectMinHeap
```
public IntegerObjectMinHeap()
```
    Constructor, with default size.
  - IntegerObjectMinHeap
```
public IntegerObjectMinHeap(int minsize)
```
    Constructor, with given minimum size.
    
    Parameters:
    minsize - Minimum size
- Method Detail
  - clear
```
public void clear()
```
    Description copied from interface: IntegerObjectHeap
    
    Clear the heap contents.
    
    Specified by:
    
    clear in interface IntegerObjectHeap<V>
  - size
```
public int size()
```
    Description copied from interface: IntegerObjectHeap
    
    Query the size
    
    Specified by:
    
    size in interface IntegerObjectHeap<V>
    
    Returns:
    Size
  - isEmpty
```
public boolean isEmpty()
```
    Description copied from interface: IntegerObjectHeap
    
    Is the heap empty?
    
    Specified by:
    
    isEmpty in interface IntegerObjectHeap<V>
    
    Returns:
    true when the size is 0.
  - add
```
public void add(int o,
       V v)
```
    Description copied from interface: IntegerObjectHeap
    
    Add a key-value pair to the heap
    
    Specified by:
    
    add in interface IntegerObjectHeap<V>
    
    Parameters:
    o - Key
    v - Value
  - add
```
public void add(int key,
       V val,
       int max)
```
    Description copied from interface: IntegerObjectHeap
    
    Add a key-value pair to the heap if it improves the top.
    
    Specified by:
    
    add in interface IntegerObjectHeap<V>
    
    Parameters:
    key - Key
    val - Value
    max - Desired maximum size
  - replaceTopElement
```
public void replaceTopElement(int reinsert,
                     V val)
```
    Description copied from interface: IntegerObjectHeap
    
    Combined operation that removes the top element, and inserts a new element instead.
    
    Specified by:
    
    replaceTopElement in interface IntegerObjectHeap<V>
    
    Parameters:
    reinsert - Key of new element
    val - Value of new element
  - heapifyUp2
```
private void heapifyUp2(int twopos,
              int 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,
              int 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: IntegerObjectHeap
    
    Remove the first element
    
    Specified by:
    
    poll in interface IntegerObjectHeap<V>
  - heapifyDown
```
private void heapifyDown(int 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,
                int 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,
                int 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 int peekKey()
```
    Description copied from interface: IntegerObjectHeap
    
    Get the current top key
    
    Specified by:
    
    peekKey in interface IntegerObjectHeap<V>
    
    Returns:
    Top key
  - peekValue
```
public V peekValue()
```
    Description copied from interface: IntegerObjectHeap
    
    Get the current top value
    
    Specified by:
    
    peekValue in interface IntegerObjectHeap<V>
    
    Returns:
    Value
  - toString
```
public String toString()
```
    Overrides:
    
    toString in class Object
  - unsortedIter
```
public IntegerObjectMinHeap.UnsortedIter unsortedIter()
```
    Description copied from interface: IntegerObjectHeap
    
    Get an unsorted iterator to inspect the heap.
    
    Specified by:
    
    unsortedIter in interface IntegerObjectHeap<V>
    
    Returns:
    Iterator

Class IntegerObjectMinHeap<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

IntegerObjectMinHeap

IntegerObjectMinHeap

Method Detail

clear

size

isEmpty

add

add

replaceTopElement

heapifyUp2

heapifyUp4

poll

heapifyDown

heapifyDown2

heapifyDown4

peekKey

peekValue

toString

unsortedIter