de.lmu.ifi.dbs.elki.utilities.datastructures.heap

Class Heap<E>

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 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.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	Heap.UnorderedIter Heap iterator.

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.

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 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.
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 Object[] queue

Heap storage.

size

protected int size

Current number of objects.

comparator

protected final Comparator<Object> comparator

The comparator or null.

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(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.

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.

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 String checkHeap()

Test whether the heap is still valid. Debug method.

Returns:

null when the heap is correct