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

java.lang.Object
- de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap<E>

Type Parameters:
E - Element type. Should be Comparable or a Comparator needs to be given.

All Implemented Interfaces:

Iterable<E>

Direct Known Subclasses:

TopBoundedHeap, UpdatableHeap
```
public class Heap<E>
extends Object
implements Iterable<E>
```
Basic in-memory heap structure. Closely related to a PriorityQueue, but here we can override methods to obtain e.g. a TopBoundedHeap Additionally, this heap is built lazily: if you first add many elements, then poll the heap, it will be bulk-loaded in O(n) instead of iteratively built in O(n log n). This is implemented via a simple validTo counter.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

protected class Heap.Itr
Iterator over queue elements.

Nested Classes
Modifier and Type	Class and Description
`protected class`	`Heap.Itr` Iterator over queue elements.

Field Summary

Fields
Modifier and Type	Field and Description
`protected Comparator<Object>`	`comparator` The comparator or `null`.
`private static int`	`DEFAULT_INITIAL_CAPACITY` Default initial capacity.
`private int`	`modCount` (Structural) modification counter.
`protected Object[]`	`queue` Heap storage.
`protected int`	`size` Current number of objects.
`protected int`	`validSize` Indicate up to where the heap is valid.

Constructor Summary

Constructors
Constructor and Description
`Heap()` Default constructor: default capacity, natural ordering.
`Heap(Comparator<? super E> comparator)` Constructor with `Comparator`.
`Heap(int size)` Constructor with initial capacity, natural ordering.
`Heap(int size, Comparator<? super E> comparator)` Constructor with initial capacity and `Comparator`.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`add(E e)` Add an element to the heap.
`protected String`	`checkHeap()` Test whether the heap is still valid.
`void`	`clear()` Clear the heap.
`protected void`	`ensureValid()` Perform pending heap repair operations in a single bulk operation.
`protected boolean`	`heapifyDown(int pos, Object reinsert)` Execute a "Heapify Downwards" aka "SiftDown".
`protected boolean`	`heapifyDownComparable(int ipos, Object reinsert)` Execute a "Heapify Downwards" aka "SiftDown".
`protected boolean`	`heapifyDownComparator(int ipos, Object cur)` Execute a "Heapify Downwards" aka "SiftDown".
`protected void`	`heapifyUp(int pos, E elem)` Execute a "Heapify Upwards" aka "SiftUp".
`protected void`	`heapifyUpComparable(int pos, Object elem)` Execute a "Heapify Upwards" aka "SiftUp".
`protected void`	`heapifyUpComparator(int pos, Object cur)` Execute a "Heapify Upwards" aka "SiftUp".
`protected void`	`heapModified()` Called at the end of each heap modification.
`boolean`	`isEmpty()` Test for emptiness.
`Iterator<E>`	`iterator()`
`E`	`peek()` Peek at the top element.
`E`	`poll()` Remove the top element.
`protected E`	`removeAt(int pos)` Remove the element at the given position.
`E`	`replaceTopElement(E e)` Combined operation that removes the top element, and inserts a new element instead.
`protected void`	`resize(int requiredSize)` Test whether we need to resize to have the requested capacity.
`int`	`size()` Get the heap size.

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

- Field Detail
  - queue
```
protected transient Object[] queue
```
    Heap storage.
  - size
```
protected int size
```
    Current number of objects.
  - validSize
```
protected int validSize
```
    Indicate up to where the heap is valid.
  - comparator
```
protected final Comparator<Object> comparator
```
    The comparator or null.
  - modCount
```
private transient int modCount
```
    (Structural) modification counter. Used to invalidate iterators.
  - DEFAULT_INITIAL_CAPACITY
```
private static final int DEFAULT_INITIAL_CAPACITY
```
    Default initial capacity.
    
    See Also:
    Constant Field Values
- Constructor Detail
  - Heap
```
public Heap()
```
    Default constructor: default capacity, natural ordering.
  - Heap
```
public Heap(int size)
```
    Constructor with initial capacity, natural ordering.
    
    Parameters:
    size - initial size
  - Heap
```
public Heap(Comparator<? super E> comparator)
```
    Constructor with Comparator.
    
    Parameters:
    comparator - Comparator
  - Heap
```
public Heap(int size,
    Comparator<? super E> comparator)
```
    Constructor with initial capacity and Comparator.
    
    Parameters:
    size - initial capacity
    comparator - Comparator
- Method Detail
  - add
```
public void add(E e)
```
    Add an element to the heap.
    
    Parameters:
    e - Element to add
  - replaceTopElement
```
public E replaceTopElement(E e)
```
    Combined operation that removes the top element, and inserts a new element instead.
    
    Parameters:
    e - New element to insert
    
    Returns:
    Previous top element of the heap
  - peek
```
public E peek()
```
    Peek at the top element.
    
    Returns:
    Top element.
  - poll
```
public E poll()
```
    Remove the top element.
    
    Returns:
    Top element.
  - ensureValid
```
protected void ensureValid()
```
    Perform pending heap repair operations in a single bulk operation.
  - removeAt
```
protected E removeAt(int pos)
```
    Remove the element at the given position.
    
    Parameters:
    pos - Element position.
    
    Returns:
    Element that was at this position.
  - heapifyUp
```
protected void heapifyUp(int pos,
             E elem)
```
    Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.
    
    Parameters:
    pos - insertion position
    elem - Element to insert
  - heapifyUpComparable
```
protected void heapifyUpComparable(int pos,
                       Object elem)
```
    Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.
    
    Parameters:
    pos - insertion position
    elem - Element to insert
  - heapifyUpComparator
```
protected void heapifyUpComparator(int pos,
                       Object cur)
```
    Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.
    
    Parameters:
    pos - insertion position
    cur - Element to insert
  - heapifyDown
```
protected boolean heapifyDown(int pos,
                  Object reinsert)
```
    Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.
    
    Parameters:
    pos - re-insertion position
    reinsert - Object to reinsert
    
    Returns:
    true when the order was changed
  - heapifyDownComparable
```
protected boolean heapifyDownComparable(int ipos,
                            Object reinsert)
```
    Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.
    
    Parameters:
    ipos - re-insertion position
    reinsert - Object to reinsert
    
    Returns:
    true when the order was changed
  - heapifyDownComparator
```
protected boolean heapifyDownComparator(int ipos,
                            Object cur)
```
    Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.
    
    Parameters:
    ipos - re-insertion position
    cur - Object to reinsert
    
    Returns:
    true when the order was changed
  - size
```
public int size()
```
    Get the heap size.
    
    Returns:
    Heap size
  - isEmpty
```
public boolean isEmpty()
```
    Test for emptiness.
    
    Returns:
    true when the heap is empty
  - resize
```
protected final void resize(int requiredSize)
```
    Test whether we need to resize to have the requested capacity.
    
    Parameters:
    requiredSize - required capacity
  - clear
```
public void clear()
```
    Clear the heap.
  - iterator
```
public Iterator<E> iterator()
```
    Specified by:
    
    iterator in interface Iterable<E>
  - heapModified
```
protected void heapModified()
```
    Called at the end of each heap modification.
  - checkHeap
```
protected String checkHeap()
```
    Test whether the heap is still valid. Debug method.
    
    Returns:
    null when the heap is correct

Class Heap<E>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

queue

size

validSize

comparator

modCount

DEFAULT_INITIAL_CAPACITY

Constructor Detail

Heap

Heap

Heap

Heap

Method Detail

add

replaceTopElement

peek

poll

ensureValid

removeAt

heapifyUp

heapifyUpComparable

heapifyUpComparator

heapifyDown

heapifyDownComparable

heapifyDownComparator

size

isEmpty

resize

clear

iterator

heapModified

checkHeap