DataStructures
Class PairHeap

java.lang.Object
  |
  +--DataStructures.PairHeap

public class PairHeap

extends java.lang.Object

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

See Also:

PairNode

Constructor Summary

PairHeap()
Construct the pairing heap.

Method Summary

void	decreaseKey(PairNode p, Comparable newVal) Change the value of the item stored in the pairing heap.
Comparable	deleteMin() Remove the smallest item from the priority queue.
Comparable	findMin() Find the smallest item in the priority queue.
PairNode	insert(Comparable x) Insert into the priority queue, and return a PairNode 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.

Methods inherited from class java.lang.Object

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

Constructor Detail

PairHeap

public PairHeap()

Construct the pairing heap.

Method Detail

insert

public PairNode insert(Comparable x)

Insert into the priority queue, and return a PairNode 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 Comparable findMin()

Find the smallest item in the priority queue.

Returns:

the smallest item, or null if empty.

deleteMin

public Comparable deleteMin()

Remove the smallest item from the priority queue.

Returns:

the smallest item, or null if empty.

decreaseKey

public void decreaseKey(PairNode p,
                        Comparable newVal)

Change the value of the item stored in the pairing heap. Does nothing if newVal is larger than the currently stored value.

Parameters:

p - any node returned by addItem.

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

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

main

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