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

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

Type Parameters:
K - Key type

All Implemented Interfaces:

ObjectHeap<K>
```
public class ComparatorMinHeap<K>
extends Object
implements ObjectHeap<K>
```
Binary heap for primitive types.

Author:

Erich Schubert

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

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

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

Field Summary

Fields
Modifier and Type	Field and Description
`protected Comparator<Object>`	`comparator` Comparator
`protected int`	`size` Current size of heap.
`private static int`	`TWO_HEAP_INITIAL_SIZE` Initial size of the 2-ary heap.
`protected Object[]`	`twoheap` Base heap.

Constructor Summary

Constructors
Constructor and Description
`ComparatorMinHeap(Comparator<? super K> comparator)` Constructor, with default size.
`ComparatorMinHeap(int minsize, Comparator<? super K> comparator)` 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(Object cur)` Invoke heapify-down for the root object.
`private void`	`heapifyUp(int twopos, Object cur)` Heapify-Up method for 2-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()`
`ComparatorMinHeap.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 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 Comparator<Object> comparator
```
    Comparator
- Constructor Detail
  - ComparatorMinHeap
```
public ComparatorMinHeap(Comparator<? super K> comparator)
```
    Constructor, with default size.
    
    Parameters:
    comparator - Comparator
  - ComparatorMinHeap
```
public ComparatorMinHeap(int minsize,
                 Comparator<? super K> comparator)
```
    Constructor, with given minimum size.
    
    Parameters:
    minsize - Minimum size
    comparator - Comparator
- Method Detail
  - clear
```
public void clear()
```
    Description copied from interface: ObjectHeap
    
    Delete all elements from the heap.
    
    Specified by:
    
    clear in interface ObjectHeap<K>
  - size
```
public int size()
```
    Description copied from interface: ObjectHeap
    
    Query the size
    
    Specified by:
    
    size in interface ObjectHeap<K>
    
    Returns:
    Size
  - isEmpty
```
public boolean isEmpty()
```
    Description copied from interface: ObjectHeap
    
    Is the heap empty?
    
    Specified by:
    
    isEmpty in interface ObjectHeap<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>
    
    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>
    
    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>
    
    Parameters:
    reinsert - New element to insert
    
    Returns:
    Previous top element of the heap
  - heapifyUp
```
private void heapifyUp(int twopos,
             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 interface ObjectHeap<K>
    
    Returns:
    Top element
  - heapifyDown
```
private void heapifyDown(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 interface ObjectHeap<K>
    
    Returns:
    Top key
  - toString
```
public String toString()
```
    Overrides:
    
    toString in class Object
  - unsortedIter
```
public ComparatorMinHeap.UnsortedIter unsortedIter()
```
    Description copied from interface: ObjectHeap
    
    Get an unsorted iterator to inspect the heap.
    
    Specified by:
    
    unsortedIter in interface ObjectHeap<K>
    
    Returns:
    Iterator

Class ComparatorMinHeap<K>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

twoheap

size

TWO_HEAP_INITIAL_SIZE

comparator

Constructor Detail

ComparatorMinHeap

ComparatorMinHeap

Method Detail

clear

size

isEmpty

add

add

replaceTopElement

heapifyUp

poll

heapifyDown

peek

toString

unsortedIter