weiss.nonstandard
Class PairingHeap

java.lang.Object
  |
  +--weiss.nonstandard.PairingHeap

All Implemented Interfaces:

PriorityQueue

public class PairingHeap

extends java.lang.Object

implements PriorityQueue

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

See Also:

PriorityQueue.Position

Inner classes inherited from class weiss.nonstandard.PriorityQueue

PriorityQueue.Position

Constructor Summary

PairingHeap()
Construct the pairing heap.

Method Summary

void	decreaseKey(PriorityQueue.Position pos, java.lang.Comparable newVal) Change the value of the item stored in the pairing heap.
java.lang.Comparable	deleteMin() Remove the smallest item from the priority queue.
java.lang.Comparable	findMin() Find the smallest item in the priority queue.
PriorityQueue.Position	insert(java.lang.Comparable 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 PriorityQueue.Position insert(java.lang.Comparable x)

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

Specified by:

insert in interface PriorityQueue

Parameters:

x - the item to insert.

Returns:

the node containing the newly inserted item.

findMin

public java.lang.Comparable findMin()

Find the smallest item in the priority queue.

Specified by:

findMin in interface PriorityQueue

Returns:

the smallest item.

Throws:

UnderflowException - if pairing heap is empty.

deleteMin

public java.lang.Comparable deleteMin()

Remove the smallest item from the priority queue.

Specified by:

deleteMin in interface PriorityQueue

Returns:

the smallest item.

Throws:

UnderflowException - if pairing heap is empty.

decreaseKey

public void decreaseKey(PriorityQueue.Position pos,
                        java.lang.Comparable newVal)

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

Specified by:

decreaseKey in interface PriorityQueue

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.

Specified by:

isEmpty in interface PriorityQueue

Returns:

true if empty, false otherwise.

size

public int size()

Returns number of items stored in the priority queue.

Specified by:

size in interface PriorityQueue

Returns:

size of the priority queue.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

Specified by:

makeEmpty in interface PriorityQueue

main

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