All Packages  Class Hierarchy  This Package  Previous  Next  Index  

Class DataStructures.PairHeap

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

public class PairHeap
extends Object
Implements a pairing heap. Supports a decreaseKey operation. Note that all "matching" is based on the compareTo method.

See Also:
PairNode

Constructor Index

 o PairHeap()
Construct the pairing heap.

Method Index

 o decreaseKey(PairNode, Comparable)
Change the value of the item stored in the pairing heap.
 o deleteMin()
Remove the smallest item from the priority queue.
 o findMin()
Find the smallest item in the priority queue.
 o insert(Comparable)
Insert into the priority queue, and return a PairNode that can be used by decreaseKey.
 o isEmpty()
Test if the priority queue is logically empty.
 o main(String[])
 o makeEmpty()
Make the priority queue logically empty.

Constructors

 o PairHeap
public PairHeap()
Construct the pairing heap.

Methods

 o 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.
 o findMin
public Comparable findMin()
Find the smallest item in the priority queue.

Returns:
the smallest item, or null if empty.
 o deleteMin
public Comparable deleteMin()
Remove the smallest item from the priority queue.

Returns:
the smallest item, or null if empty.
 o 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.
 o isEmpty
public boolean isEmpty()
Test if the priority queue is logically empty.

Returns:
true if empty, false otherwise.
 o makeEmpty
public void makeEmpty()
Make the priority queue logically empty.

 o main
public static void main(String[] args)

All Packages  Class Hierarchy  This Package  Previous  Next  Index