com.kuka.graph.util
Class PairingHeap<E>

java.lang.Object
  com.kuka.graph.util.PairingHeap<E>

Type Parameters:

E - the type of elements held in this priority queue

All Implemented Interfaces:

PriorityQueue<E>

public class PairingHeap<E>
extends Object
implements PriorityQueue<E>

Implements a pairing heap. Supports a decreaseKey operation.

Nested Class Summary

Nested classes/interfaces inherited from interface com.kuka.graph.util.PriorityQueue

PriorityQueue.Handle<T>

Constructor Summary

PairingHeap()
Creates a PairingHeap that orders its elements according to their natural ordering.

PairingHeap(Comparator<? super E> comparator)
Creates a PairingHeap that orders its elements according to the specified comparator.

Method Summary

PriorityQueue.Handle<E>	add(E value) Adds an element to this priority queue, maintaining heap order.
void	clear() Removes all of the elements from this priority queue.
void	decreaseKey(PriorityQueue.Handle<E> item, E element) Changes the value of the item stored in the pairing heap (optional operation).
PriorityQueue.Handle<E>	findMin() Finds and returns the item with the lowest priority in this queue.
boolean	isEmpty() Returns true if this priority queue contains no elements.
E	removeMin() Removes and returns the item with the lowest priority from this queue.
int	size() Returns the number of elements in this priority queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

PairingHeap

public PairingHeap()

Creates a PairingHeap that orders its elements according to their natural ordering.

PairingHeap

public PairingHeap(Comparator<? super E> comparator)

Creates a PairingHeap that orders its elements according to the specified comparator. If the comparator is null, the natural ordering of the elements will be used.

Parameters:

comparator - the comparator that will be used to order this priority queue

Method Detail

size

public int size()

Description copied from interface: PriorityQueue

Returns the number of elements in this priority queue.

Specified by:

size in interface PriorityQueue<E>

Returns:

the number of elements in this priority queue

isEmpty

public boolean isEmpty()

Description copied from interface: PriorityQueue

Returns true if this priority queue contains no elements.

Specified by:

isEmpty in interface PriorityQueue<E>

Returns:

true if this priority queue contains no elements

add

public PriorityQueue.Handle<E> add(E value)

Description copied from interface: PriorityQueue

Adds an element to this priority queue, maintaining heap order. Duplicates are allowed.

Specified by:

add in interface PriorityQueue<E>

Parameters:

value - the value of the item to insert

Returns:

a handle for modifying the priority of the element with PriorityQueue.decreaseKey(Handle, Object)

findMin

public PriorityQueue.Handle<E> findMin()

Description copied from interface: PriorityQueue

Finds and returns the item with the lowest priority in this queue.

Specified by:

findMin in interface PriorityQueue<E>

Returns:

the item with the lowest priority

See Also:

PriorityQueue.removeMin()

removeMin

public E removeMin()

Description copied from interface: PriorityQueue

Removes and returns the item with the lowest priority from this queue.

Specified by:

removeMin in interface PriorityQueue<E>

Returns:

the item with the lowest priority

See Also:

PriorityQueue.findMin()

decreaseKey

public void decreaseKey(PriorityQueue.Handle<E> item,
                        E element)

Description copied from interface: PriorityQueue

Changes the value of the item stored in the pairing heap (optional operation).

The given handle must be valid. A handle is valid as long as it is an element of this priority queue. When the corresponding value is removed from the queue the handle is invalid. To check whether a handle is valid call PriorityQueue.Handle.isValid(). Note that this is considered an advanced operation and might not be supported by all priority queues.

Specified by:

decreaseKey in interface PriorityQueue<E>

Parameters:

item - a valid handle returned by PriorityQueue.add(Object)

element - the new element, which must be smaller than the currently stored one

clear

public void clear()

Description copied from interface: PriorityQueue

Removes all of the elements from this priority queue. The priority queue will be empty after this method returns.

Specified by:

clear in interface PriorityQueue<E>