weiss.nonstandard
Class PairingHeap<AnyType extends java.lang.Comparable<? super AnyType>>

java.lang.Object
  weiss.nonstandard.PairingHeap<AnyType>

public class PairingHeap<AnyType extends java.lang.Comparable<? super AnyType>>
extends java.lang.Object

Implements a pairing heap. Supports a decreaseKey operation. Note that all "matching" is based on the compareTo method.

See Also:

PriorityQueue.Position

Nested Class Summary

static interface

PairingHeap.Position<AnyType> The Position interface represents a type that can be used for the decreaseKey operation.

Constructor Summary

PairingHeap()
Construct the pairing heap.

Method Summary

void	decreaseKey(PairingHeap.Position<AnyType> pos, AnyType newVal) Change the value of the item stored in the pairing heap.
AnyType	deleteMin() Remove the smallest item from the priority queue.
AnyType	findMin() Find the smallest item in the priority queue.
PairingHeap.Position<AnyType>	insert(AnyType x) Insert into the priority queue, and return a Position that can be used by decreaseKey.
boolean	isEmpty() Test if the priority queue is logically empty.
static void	main(java.lang.String[] args)
void	makeEmpty() Make the priority queue logically empty.
int	size() Returns number of items stored in the 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()

Construct the pairing heap.

Method Detail

insert

public PairingHeap.Position<AnyType> insert(AnyType x)

Insert into the priority queue, and return a Position that can be used by decreaseKey. Duplicates are allowed.

Parameters:

x - the item to insert.

Returns:

the node containing the newly inserted item.

findMin

public AnyType findMin()

Find the smallest item in the priority queue.

Returns:

the smallest item.

Throws:

UnderflowException - if pairing heap is empty.

deleteMin

public AnyType deleteMin()

Remove the smallest item from the priority queue.

Returns:

the smallest item.

Throws:

UnderflowException - if pairing heap is empty.

decreaseKey

public void decreaseKey(PairingHeap.Position<AnyType> pos,
                        AnyType newVal)

Change the value of the item stored in the pairing heap.

Parameters:

pos - any Position returned by insert.

newVal - the new value, which must be smaller than the currently stored value.

Throws:

java.lang.IllegalArgumentException - if pos is null.

IllegalValueException - if new value is larger than old.

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

size

public int size()

Returns number of items stored in the priority queue.

Returns:

size of the priority queue.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

main

public static void main(java.lang.String[] args)