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.

Direct Known Subclasses:

TopBoundedHeap, UpdatableHeap
```
public class Heap<E>
extends java.lang.Object
```
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.

Since:

0.4.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

class Heap.UnorderedIter
Heap iterator.

Nested Classes
Modifier and Type	Class and Description
`class`	`Heap.UnorderedIter` Heap iterator.

Field Summary

Fields
Modifier and Type	Field and Description
`protected java.util.Comparator<java.lang.Object>`	`comparator` The comparator.
`private static int`	`DEFAULT_INITIAL_CAPACITY` Default initial capacity.
`private int`	`modCount` (Structural) modification counter.
`protected java.lang.Object[]`	`queue` Heap storage.
`protected int`	`size` Current number of objects.

Constructor Summary

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

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`add(E e)` Add an element to the heap.
`protected java.lang.String`	`checkHeap()` Test whether the heap is still valid.
`void`	`clear()` Clear the heap.
`protected boolean`	`heapifyDown(int ipos, java.lang.Object cur)` Execute a "Heapify Downwards" aka "SiftDown".
`protected void`	`heapifyUp(int pos, E elem)` Execute a "Heapify Upwards" aka "SiftUp".
`protected void`	`heapModified()` Called at the end of each heap modification.
`boolean`	`isEmpty()` Test for emptiness.
`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.
`Heap.UnorderedIter`	`unorderedIter()` Get an unordered heap iterator.

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

- Field Detail
  - queue
```
protected java.lang.Object[] queue
```
    Heap storage.
  - size
```
protected int size
```
    Current number of objects.
  - comparator
```
protected final java.util.Comparator<java.lang.Object> comparator
```
    The comparator.
  - modCount
```
private 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(java.util.Comparator<? super E> comparator)
```
    Constructor with Comparator.
    
    Parameters:
    
    comparator - Comparator
  - Heap
```
public Heap(int size,
            java.util.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.
  - 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
  - heapifyDown
```
protected boolean heapifyDown(int ipos,
                              java.lang.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.
  - heapModified
```
protected void heapModified()
```
    Called at the end of each heap modification.
  - unorderedIter
```
public Heap.UnorderedIter unorderedIter()
```
    Get an unordered heap iterator.
    
    Returns:
    
    Iterator.
  - checkHeap
```
protected java.lang.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

comparator

modCount

DEFAULT_INITIAL_CAPACITY

Constructor Detail

Heap

Heap

Heap

Heap

Method Detail

add

replaceTopElement

peek

poll

removeAt

heapifyUp

heapifyDown

size

isEmpty

resize

clear

heapModified

unorderedIter

checkHeap