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

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

All Implemented Interfaces:

Heap<K,V>, Serializable

Direct Known Subclasses:

Deap

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

A double-ended priority queue implemented as a binary heap. This heap provides access to the minimum and the maximums elements in the queue. Elements stored in this heap must be instances of HeapNode<\code> (@see HeapNode).

Author:

Elke Achtert

See Also:

Serialized Form

Field Summary

(package private) Vector<HeapNode<K,V>>	heap Contains all elements of the heap.
(package 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

MinMaxHeap()
Constructs and initialises a new min-max-heap.

Method Summary

void	addNode(HeapNode<K,V> node) Adds a node to this heap.
private void	bubbleUp() Reestablishes the min-max ordering after insertion of a new element.
private void	bubbleUpMax(int index) Bubbles up a maximum.
private void	bubbleUpMin(int index) Bubbles up a minimum.
void	flowUp(int index) Moves up a node at the specified index until it satisfies the heaporder.
private int	getGrandParent(int index) Returns the index of the grand parents.
private int	getGreatestChild(int index) Returns the index of the greater child.
private int	getGreatestChildAndGrandChild(int index) Returns the index of the greatest of the children and grand children.
private int	getGreatestGrandChild(int index) Returns the index of the greatest grand child.
Integer	getIndexOf(V value) Returns the current index of the specified value in this heap.
private int	getLeftChild(int index) Returns the index of the left child.
HeapNode<K,V>	getMaxNode() Retrieves and removes the maximum node of this heap.
HeapNode<K,V>	getMinNode() Retrieves and removes the minimum node of this heap.
HeapNode<K,V>	getNodeAt(int index) Returns an element of the heap by the index.
private int	getParent(int index) Returns the index of the parent of the element at the specified index.
private int	getRightChild(int index) Returns the index of the right child.
private int	getSmallestChild(int index) Returns the index of the smaller child.
private int	getSmallestChildAndGrandChild(int index) Returns the index of the smallest of the children and grand children.
private int	getSmallestGrandChild(int index) Returns the index of the smallest grand child.
private boolean	hasChildren(int index) Checks if the element has children.
private boolean	hasGrandChildren(int index) Checks if the element has grand children.
private boolean	hasGrandParent(int index) Checks if the element has a grand parent.
private boolean	hasParents(int index) Checks if the element has parents.
boolean	isEmpty() Indicates wether this heap ist empty.
private boolean	isMaxLevel(int index) Checks if the specified index is in a max level.
HeapNode<K,V>	maxNode() Retrieves, but does not remove, the maximum node of this heap.
HeapNode<K,V>	minNode() Retrieves, but does not remove, the minmum node of this heap.
int	size() Returns the size of the heap.
private void	swap(int firstIndex, int secondIndex) Swaps the position of two elements.
String	toString() Returns a string representation of the object.
private void	trickleDown(int index) The trickle down method.
private void	trickleDownMax(int index) Trickles down a maximum.
private void	trickleDownMin(int index) Trickles down a minimum.

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

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

Contains all elements of the heap.

indices

Hashtable<Integer,Integer> indices

Holds the indices in the heap of each element.

Constructor Detail

MinMaxHeap

public MinMaxHeap()

Constructs and initialises a new min-max-heap.

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

minNode

public final HeapNode<K,V> minNode()

Retrieves, but does not remove, the minmum node of this heap. If the heap is empty, null will be returned.

Returns:

The minimum node of this heap, null in case of emptyness.

getMaxNode

public HeapNode<K,V> getMaxNode()

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

Returns:

The maximum node of this heap, null in case of emptyness.

maxNode

public final HeapNode<K,V> maxNode()

Retrieves, but does not remove, the maximum node of this heap. If the heap is empty, null will be returned.

Returns:

The maximum node of this heap, null in case of emptyness.

getNodeAt

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

Returns an element of the heap by the index. If the index is not valid

null is returned.

Specified by:

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

Parameters:

index - the index of the element

Returns:

the element

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

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

Specified by:

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

Returns:

the size

isEmpty

public 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

toString

public String toString()

Returns a string representation of the object.

Overrides:

toString in class Object

Returns:

a string representation of the object.

swap

private void swap(int firstIndex,
                  int secondIndex)

Swaps the position of two elements.

Parameters:

firstIndex - index of the first element

secondIndex - index of the second element

bubbleUp

private void bubbleUp()

Reestablishes the min-max ordering after insertion of a new element.

bubbleUpMin

private void bubbleUpMin(int index)

Bubbles up a minimum.

Parameters:

index - index of the element to bubble up

bubbleUpMax

private void bubbleUpMax(int index)

Bubbles up a maximum.

Parameters:

index - index of the element to bubble up

trickleDown

private void trickleDown(int index)

The trickle down method.

Parameters:

index - index of the element to trickle down

trickleDownMin

private void trickleDownMin(int index)

Trickles down a minimum.

Parameters:

index - index of the element to trickle down

trickleDownMax

private void trickleDownMax(int index)

Trickles down a maximum.

Parameters:

index - index of the element to trickle down

getSmallestChild

private int getSmallestChild(int index)

Returns the index of the smaller child.

Parameters:

index - index of the element

Returns:

index of the smaller child

getSmallestGrandChild

private int getSmallestGrandChild(int index)

Returns the index of the smallest grand child.

Parameters:

index - index of the element

Returns:

index of the smallest grand child

getSmallestChildAndGrandChild

private int getSmallestChildAndGrandChild(int index)

Returns the index of the smallest of the children and grand children.

Parameters:

index - index of the element

Returns:

index of the smallest of the children and grand children

getGreatestChild

private int getGreatestChild(int index)

Returns the index of the greater child.

Parameters:

index - index of the element

Returns:

index of the greater child

getGreatestGrandChild

private int getGreatestGrandChild(int index)

Returns the index of the greatest grand child.

Parameters:

index - index of the element

Returns:

index of the greatest grand child

getGreatestChildAndGrandChild

private int getGreatestChildAndGrandChild(int index)

Returns the index of the greatest of the children and grand children.

Parameters:

index - index of the element

Returns:

index of the greatest of the children and grand children

getParent

private int getParent(int index)

Returns the index of the parent of the element at the specified index.

Parameters:

index - the index of the element

Returns:

the index of the parent element

getLeftChild

private int getLeftChild(int index)

Returns the index of the left child.

Parameters:

index - index of the element

Returns:

index of the left child

getRightChild

private int getRightChild(int index)

Returns the index of the right child.

Parameters:

index - index of the element

Returns:

index of the right child

getGrandParent

private int getGrandParent(int index)

Returns the index of the grand parents.

Parameters:

index - index of the element

Returns:

index of the grand parents

hasParents

private boolean hasParents(int index)

Checks if the element has parents.

Parameters:

index - index of the element

Returns:

true if the element has parents

hasGrandParent

private boolean hasGrandParent(int index)

Checks if the element has a grand parent.

Parameters:

index - index of the element

Returns:

true if the element has a grand parent

hasChildren

private boolean hasChildren(int index)

Checks if the element has children.

Parameters:

index - index of the element

Returns:

true if the element has children

hasGrandChildren

private boolean hasGrandChildren(int index)

Checks if the element has grand children.

Parameters:

index - index of the element

Returns:

true if the element has grand children

isMaxLevel

private boolean isMaxLevel(int index)

Checks if the specified index is in a max level.

Parameters:

index - the index to be tested

Returns:

true if the specified index is in a max level