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

Class Heap<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<E>

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:

Serializable, Iterable<E>, Collection<E>, Queue<E>

Direct Known Subclasses:

TopBoundedHeap, UpdatableHeap

public class Heap<E>
extends AbstractQueue<E>
implements Serializable

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.

See Also:

Serialized Form

Nested Class Summary

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
int	modCount (Structural) modification counter.
protected Object[]	queue Heap storage
private static long	serialVersionUID Serial version
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
boolean	add(E e)
boolean	addAll(Collection<? extends E> c)
protected E	castQueueElement(int n)
protected String	checkHeap() Test whether the heap is still valid.
void	clear()
boolean	contains(Object o)
protected void	ensureValid() Repair 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".
Iterator<E>	iterator()
boolean	offer(E e)
E	peek()
E	poll()
protected E	removeAt(int pos) Remove the element at the given position.
protected void	resize(int requiredSize) Test whether we need to resize to have the requested capacity.
int	size()
ArrayList<E>	toSortedArrayList() Return the heap as a sorted array list, by repeated polling.

Methods inherited from class java.util.AbstractQueue

element, remove

Methods inherited from class java.util.AbstractCollection

containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray

Field Detail

serialVersionUID

private static final long serialVersionUID

Serial version

See Also:

Constant Field Values

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

public 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 boolean add(E e)

Specified by:

add in interface Collection<E>

Specified by:

add in interface Queue<E>

Overrides:

add in class AbstractQueue<E>

offer

public boolean offer(E e)

Specified by:

offer in interface Queue<E>

peek

public E peek()

Specified by:

peek in interface Queue<E>

poll

public E poll()

Specified by:

poll in interface Queue<E>

ensureValid

protected void ensureValid()

Repair the heap

removeAt

protected E removeAt(int pos)

Remove the element at the given position.

Parameters:

pos - Element 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

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

Returns:

true when the order was changed

castQueueElement

protected final E castQueueElement(int n)

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in class AbstractCollection<E>

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

Specified by:

clear in interface Collection<E>

Overrides:

clear in class AbstractQueue<E>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<E>

Overrides:

contains in class AbstractCollection<E>

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in class AbstractCollection<E>

addAll

public boolean addAll(Collection<? extends E> c)

Specified by:

addAll in interface Collection<E>

Overrides:

addAll in class AbstractQueue<E>

toSortedArrayList

public ArrayList<E> toSortedArrayList()

Return the heap as a sorted array list, by repeated polling. This will empty the heap!

Returns:

new array list

checkHeap

protected String checkHeap()

Test whether the heap is still valid. Debug method.

Returns:

null when the heap is correct