de.lmu.ifi.dbs.elki.utilities.heap
Class DefaultHeap<K extends Comparable<K>,V extends Identifiable>

java.lang.Object
  de.lmu.ifi.dbs.elki.utilities.heap.DefaultHeap<K,V>

All Implemented Interfaces:

Heap<K,V>, Serializable

public class DefaultHeap<K extends Comparable<K>,V extends Identifiable>
extends Object
implements Heap<K,V>

Implementation of a heap-based priority queue. This heap orders elements according to their natural order. Elements stored in this heap must be instances of HeapNode<\code> (@see HeapNode).

Author:

Elke Achtert

See Also:

Serialized Form

Field Summary

private boolean	ascending Indicates weather this heap is organised in ascending or descending order.
private Vector<HeapNode<K,V>>	heap Contains all elements of the heap.
private Hashtable<Integer,Integer>	indices Holds the indices in the heap of each element.
private static int	NULL_INDEX Indicates the index null.

Constructor Summary

DefaultHeap()
Creates a new heap that stores the elements in ascending order.

DefaultHeap(boolean ascending)
Creates a new heap that stores the elements in the specified order.

Method Summary

void	addNode(HeapNode<K,V> node) Adds a node to this heap.
void	clear() Clears the heap.
Vector<HeapNode<K,V>>	copy() Returns a copy of the vector holding this heap.
protected void	flowDown(int i) Moves down a node at index i until it satisfies the heaporder.
void	flowUp(int index) Moves up a node at the specified index until it satisfies the heaporder.
Integer	getIndexOf(V value) Returns the current index of the specified value in this heap.
HeapNode<K,V>	getMinNode() Retrieves and removes the minimum node of this heap.
HeapNode<K,V>	getNodeAt(int index) Returns the node at the specified index.
protected void	heapify(int i) Heapifies the subtree located at i.
protected int	heapifyLocally(int i) Heap order node at index i with respect to its both children.
protected int	indexOf(int i) Return the index of the node at index i in this heap if i is in heap, otherwise nullIndex.
boolean	isEmpty() Indicates wether this heap ist empty.
protected boolean	isGreaterThan(int i1, int i2) Return true if the node at index i1 is lower than the node at index i2.
protected boolean	isLowerThan(int i1, int i2) Return true if the node at index i1 is lower than the node at index i2.
protected int	leftChild(int i) Return the index of the left child of of the node at index i, nullIndex if there is no such child.
protected int	minChild(int i) Returns the index of the smaller child of the node at index i.
protected int	parent(int k) Returns the index of the parent of the node at index k, nullIndex if k is the root.
protected HeapNode<K,V>	removeMin() Removes and returns the minimum node from this heap and restores the heap.
protected int	rightChild(int i) Return the index of the right child of of the node at index i, nullIndex if there is no such child.
int	size() Returns the size of this heap.
protected void	swap(int i1, int i2) Swaps the nodes at the indices i1 and i2 in the array.
String	toString() Returns a string representation of this heap.

Methods inherited from class java.lang.Object

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

Field Detail

NULL_INDEX

private static final int NULL_INDEX

Indicates the index null.

See Also:

Constant Field Values

heap

private Vector<HeapNode<K extends Comparable<K>,V extends Identifiable>> heap

Contains all elements of the heap.

indices

private Hashtable<Integer,Integer> indices

Holds the indices in the heap of each element.

ascending

private boolean ascending

Indicates weather this heap is organised in ascending or descending order.

Constructor Detail

DefaultHeap

public DefaultHeap()

Creates a new heap that stores the elements in ascending order.

DefaultHeap

public DefaultHeap(boolean ascending)

Creates a new heap that stores the elements in the specified order.

Parameters:

ascending - if true, the heap is organised in ascending order, otherwise the heap is organised in descending other

Method Detail

addNode

public void addNode(HeapNode<K,V> node)

Adds a node to this heap.

Specified by:

addNode in interface Heap<K extends Comparable<K>,V extends Identifiable>

Parameters:

node - the node to be added

getMinNode

public HeapNode<K,V> getMinNode()

Retrieves and removes the minimum node of this heap. If the heap is empty, null will be returned.

Specified by:

getMinNode in interface Heap<K extends Comparable<K>,V extends Identifiable>

Returns:

the minimum node of this heap, null in case of emptyness

isEmpty

public final boolean isEmpty()

Indicates wether this heap ist empty.

Specified by:

isEmpty in interface Heap<K extends Comparable<K>,V extends Identifiable>

Returns:

true if this heap is empty, false otherwise

getIndexOf

public Integer getIndexOf(V value)

Returns the current index of the specified value in this heap.

Specified by:

getIndexOf in interface Heap<K extends Comparable<K>,V extends Identifiable>

Parameters:

value - the value for which the index should be returned

Returns:

the current index of the specified value in this heap

getNodeAt

public final HeapNode<K,V> getNodeAt(int index)

Returns the node at the specified index.

Specified by:

getNodeAt in interface Heap<K extends Comparable<K>,V extends Identifiable>

Parameters:

index - the index of the node to be returned

Returns:

the node at the specified index

flowUp

public void flowUp(int index)

Moves up a node at the specified index until it satisfies the heaporder.

Specified by:

flowUp in interface Heap<K extends Comparable<K>,V extends Identifiable>

Parameters:

index - the index of the node to be moved up.

size

public int size()

Returns the size of this heap.

Specified by:

size in interface Heap<K extends Comparable<K>,V extends Identifiable>

Returns:

the size of this heap

clear

public void clear()

Clears the heap.

copy

public Vector<HeapNode<K,V>> copy()

Returns a copy of the vector holding this heap.

Returns:

a copy of the vector holding this heap

flowDown

protected final void flowDown(int i)

Moves down a node at index i until it satisfies the heaporder.

Parameters:

i - The index of the node to be moved down.

removeMin

protected HeapNode<K,V> removeMin()

Removes and returns the minimum node from this heap and restores the heap. Returns The minimum node of this heap.

Returns:

the minimum node from this heap

swap

protected final void swap(int i1,
                          int i2)

Swaps the nodes at the indices i1 and i2 in the array.

Parameters:

i1 - the first index

i2 - the second index

heapify

protected final void heapify(int i)

Heapifies the subtree located at i. Precondition: i's both childtrees are heapordered

Parameters:

i - the idex of the subtree to be heapified

heapifyLocally

protected final int heapifyLocally(int i)

Heap order node at index i with respect to its both children. If keys had to be swapped return the new index of the node formerly located at i, nullIndex otherwise

Parameters:

i - The index of the node to be heapified.

Returns:

The new index of the node formerly located at i if keys had to be swapped, nullIndex otherwise

minChild

protected final int minChild(int i)

Returns the index of the smaller child of the node at index i. Returns nullIndex if the node is a leaf.

Parameters:

i - The index of the node

Returns:

nullIndex if the node is a leaf, the index of the smaller child otherwise.

leftChild

protected final int leftChild(int i)

Return the index of the left child of of the node at index i, nullIndex if there is no such child.

Parameters:

i - The index of the node.

Returns:

The index of the left child of of the node at index i, nullIndex if there is no such child.

rightChild

protected final int rightChild(int i)

Return the index of the right child of of the node at index i, nullIndex if there is no such child.

Parameters:

i - The index of the node.

Returns:

The index of the right child of of the node at index i, nullIndex if there is no such child.

parent

protected final int parent(int k)

Returns the index of the parent of the node at index k, nullIndex if k is the root.

Parameters:

k - The index of the node.

Returns:

The parent of the node at index k, nullIndex if k is the root

indexOf

protected final int indexOf(int i)

Return the index of the node at index i in this heap if i is in heap, otherwise nullIndex.

Parameters:

i - The index of the node.

Returns:

i if the index is in heap, otherwise nullIndex

isLowerThan

protected final boolean isLowerThan(int i1,
                                    int i2)

Return true if the node at index i1 is lower than the node at index i2.

Parameters:

i1 - The index of the first node to be tested.

i2 - The index of the second node to be tested.

Returns:

True if the node at index i1 is lower than the node at index i2, false otherwise.

isGreaterThan

protected final boolean isGreaterThan(int i1,
                                      int i2)

Return true if the node at index i1 is lower than the node at index i2.

Parameters:

i1 - The index of the first node to be tested.

i2 - The index of the second node to be tested.

Returns:

True if the node at index i1 is lower than the node at index i2, false otherwise.

toString

public String toString()

Returns a string representation of this heap.

Overrides:

toString in class Object

Returns:

a string representation of this heap