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

java.lang.Object
- de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap<K>

Type Parameters:
K - Key type

All Implemented Interfaces:

ObjectHeap<K>
```
public class ComparableMinHeap<K extends Comparable<? super K>>
extends Object
implements ObjectHeap<K>
```
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 type: Comparable 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 ComparableMinHeap.UnsortedIter
Unsorted iterator - in heap order.

Nested Classes
Modifier and Type	Class and Description
`private class`	`ComparableMinHeap.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 Comparable<Object>[]`	`fourheap` Extension heap.
`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 Comparable<Object>[]`	`twoheap` Base heap.

Constructor Summary

Constructors
Constructor and Description

ComparableMinHeap()
Constructor, with default size.

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

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

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`add(K o)` Add a key-value pair to the heap
`void`	`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(Comparable<Object> reinsert)` Invoke heapify-down for the root object.
`private void`	`heapifyDown2(int twopos, Comparable<Object> cur)` Heapify-Down for 2-ary heap.
`private void`	`heapifyDown4(int fourpos, Comparable<Object> cur)` Heapify-Down for 4-ary heap.
`private void`	`heapifyUp2(int twopos, Comparable<Object> cur)` Heapify-Up method for 2-ary heap.
`private void`	`heapifyUp4(int fourpos, Comparable<Object> cur)` Heapify-Up method for 4-ary heap.
`boolean`	`isEmpty()` Is the heap empty?
`K`	`peek()` Get the current top key
`K`	`poll()` Remove the first element
`K`	`replaceTopElement(K reinsert)` Combined operation that removes the top element, and inserts a new element instead.
`int`	`size()` Query the size
`String`	`toString()`
`ComparableMinHeap.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 Comparable<Object>[] twoheap
```
    Base heap.
  - fourheap
```
protected Comparable<Object>[] fourheap
```
    Extension heap.
  - 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
  - ComparableMinHeap
```
public ComparableMinHeap()
```
    Constructor, with default size.
  - ComparableMinHeap
```
public ComparableMinHeap(int minsize)
```
    Constructor, with given minimum size.
    
    Parameters:
    minsize - Minimum size
- Method Detail
  - clear
```
public void clear()
```
    Description copied from interface: ObjectHeap
    
    Delete all elements from the heap.
    
    Specified by:
    
    clear in interface ObjectHeap<K extends Comparable<? super K>>
  - size
```
public int size()
```
    Description copied from interface: ObjectHeap
    
    Query the size
    
    Specified by:
    
    size in interface ObjectHeap<K extends Comparable<? super K>>
    
    Returns:
    Size
  - isEmpty
```
public boolean isEmpty()
```
    Description copied from interface: ObjectHeap
    
    Is the heap empty?
    
    Specified by:
    
    isEmpty in interface ObjectHeap<K extends Comparable<? super 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 interface ObjectHeap<K extends Comparable<? super 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 interface ObjectHeap<K extends Comparable<? super K>>
    
    Parameters:
    key - Key
    max - 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 interface ObjectHeap<K extends Comparable<? super K>>
    
    Parameters:
    reinsert - New element to insert
    
    Returns:
    Previous top element of the heap
  - heapifyUp2
```
private void heapifyUp2(int twopos,
              Comparable<Object> cur)
```
    Heapify-Up method for 2-ary heap.
    
    Parameters:
    twopos - Position in 2-ary heap.
    cur - Current object
  - heapifyUp4
```
private void heapifyUp4(int fourpos,
              Comparable<Object> cur)
```
    Heapify-Up method for 4-ary heap.
    
    Parameters:
    fourpos - Position in 4-ary heap.
    cur - Current object
  - poll
```
public K poll()
```
    Description copied from interface: ObjectHeap
    
    Remove the first element
    
    Specified by:
    
    poll in interface ObjectHeap<K extends Comparable<? super K>>
    
    Returns:
    Top element
  - heapifyDown
```
private void heapifyDown(Comparable<Object> reinsert)
```
    Invoke heapify-down for the root object.
    
    Parameters:
    reinsert - Object to insert.
  - heapifyDown2
```
private void heapifyDown2(int twopos,
                Comparable<Object> cur)
```
    Heapify-Down for 2-ary heap.
    
    Parameters:
    twopos - Position in 2-ary heap.
    cur - Current object
  - heapifyDown4
```
private void heapifyDown4(int fourpos,
                Comparable<Object> cur)
```
    Heapify-Down for 4-ary heap.
    
    Parameters:
    fourpos - Position in 4-ary heap.
    cur - Current object
  - peek
```
public K peek()
```
    Description copied from interface: ObjectHeap
    
    Get the current top key
    
    Specified by:
    
    peek in interface ObjectHeap<K extends Comparable<? super K>>
    
    Returns:
    Top key
  - toString
```
public String toString()
```
    Overrides:
    
    toString in class Object
  - unsortedIter
```
public ComparableMinHeap.UnsortedIter unsortedIter()
```
    Description copied from interface: ObjectHeap
    
    Get an unsorted iterator to inspect the heap.
    
    Specified by:
    
    unsortedIter in interface ObjectHeap<K extends Comparable<? super K>>
    
    Returns:
    Iterator

Class ComparableMinHeap<K extends Comparable<? super K>>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

twoheap

fourheap

size

modCount

TWO_HEAP_MAX_SIZE

TWO_HEAP_INITIAL_SIZE

FOUR_HEAP_INITIAL_SIZE

Constructor Detail

ComparableMinHeap

ComparableMinHeap

Method Detail

clear

size

isEmpty

add

add

replaceTopElement

heapifyUp2

heapifyUp4

poll

heapifyDown

heapifyDown2

heapifyDown4

peek

toString

unsortedIter