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

See Also:

Serialized Form

Nested Class Summary

protected class

Heap.Itr Iterator over queue elements.

Field Summary

private Comparator<? super E>	comparator The comparator or null
private static int	DEFAULT_INITIAL_CAPACITY Default initial capacity
int	modCount (Structural) modification counter.
private Object[]	queue Heap storage Note: keep private; all write access should be done through putInQueue(int, java.lang.Object) for subclasses to track!
private static long	serialVersionUID Serial version
protected int	size Current number of objects

Constructor Summary

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

protected E	castQueueElement(int n)
void	clear()
protected int	compare(int pos1, int pos2)
protected int	compareExternal(E o1, int pos2)
protected int	compareExternalExternal(E o1, E o2)
private void	considerResize(int requiredSize) Test whether we need to resize to have the requested capacity.
boolean	contains(Object o)
private void	grow(int newsize) Execute the actual resize operation.
protected void	heapifyDown(int pos) Execute a "Heapify Downwards" aka "SiftDown".
protected void	heapifyUp(int pos) Execute a "Heapify Upwards" aka "SiftUp".
protected void	heapifyUpParent(int pos) Start a heapify up at the parent of this node, since we've changed a child
Iterator<E>	iterator()
private int	leftChild(int pos) Compute left child index in heap array.
boolean	offer(E e)
private int	parent(int pos) Compute parent index in heap array.
E	peek()
E	poll()
protected void	putInQueue(int index, Object e) Put an element into the queue at a given position.
protected E	removeAt(int pos) Remove the element at the given position.
private int	rightChild(int pos) Compute right child index in heap array.
int	size()
protected void	swap(int a, int b) Swap two elements in the heap.
ArrayList<E>	toSortedArrayList() Return the heap as a sorted array list, by repeated polling.

Methods inherited from class java.util.AbstractQueue

add, addAll, 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

private Object[] queue

Heap storage Note: keep private; all write access should be done through putInQueue(int, java.lang.Object) for subclasses to track!

size

protected int size

Current number of objects

comparator

private final Comparator<? super E> 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

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>

removeAt

protected E removeAt(int pos)

Remove the element at the given position.

Parameters:

pos - Element position.

parent

private int parent(int pos)

Compute parent index in heap array.

Parameters:

pos - Element index

Returns:

Parent index

leftChild

private int leftChild(int pos)

Compute left child index in heap array.

Parameters:

pos - Element index

Returns:

left child index

rightChild

private int rightChild(int pos)

Compute right child index in heap array.

Parameters:

pos - Element index

Returns:

right child index

heapifyUp

protected void heapifyUp(int pos)

Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.

Parameters:

pos - insertion position

heapifyUpParent

protected void heapifyUpParent(int pos)

Start a heapify up at the parent of this node, since we've changed a child

Parameters:

pos - Position to start the modification.

heapifyDown

protected void heapifyDown(int pos)

Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.

Parameters:

pos - re-insertion position

putInQueue

protected void putInQueue(int index,
                          Object e)

Put an element into the queue at a given position. This allows subclasses to index the queue.

Parameters:

index - Index

e - Element

swap

protected void swap(int a,
                    int b)

Swap two elements in the heap.

Parameters:

a - Element

b - Element

compare

protected int compare(int pos1,
                      int pos2)

compareExternal

protected int compareExternal(E o1,
                              int pos2)

compareExternalExternal

protected int compareExternalExternal(E o1,
                                      E o2)

castQueueElement

protected E castQueueElement(int n)

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in class AbstractCollection<E>

considerResize

private void considerResize(int requiredSize)

Test whether we need to resize to have the requested capacity.

Parameters:

requiredSize - required capacity

grow

private void grow(int newsize)

Execute the actual resize operation.

Parameters:

newsize - New size

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>

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