All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class tw.edu.ncnu.im.cnclab.DataStru.PairHeap 

java.lang.Object
   |
   +----tw.edu.ncnu.im.cnclab.DataStru.PairHeap
public class PairHeap
extends Object
implements PriorityQueue
Implements a pairing heap. Supports a decreaseKey operation, but requires use of addItem instead of insert. Heap order is always maintained; no lazy operations allowed. Note that all "matching" is based on the compares method.

Author:
Origional from Mark Allen Weiss , modified by Ding-Yi Chen on Apr 15, 1999.
See Also:
PairNode

Constructor Index

o PairHeap()
Construct the pairing heap.

Method Index

o addItem(Comparable11)
Insert into the priority queue, and return a PairNode that can be used by decreaseKey.
o decreaseKey(PairNode, Comparable11)
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(Comparable11)
Insert into the priority queue.
o isEmpty()
Test if the priority queue is logically empty.
o makeEmpty()
Make the priority queue logically empty.
o toss(Comparable11)
Insert into the priority queue, without maintaining heap order.
o validate()

Constructors

o PairHeap 
 public PairHeap()
Construct the pairing heap.

Methods

o insert 
 public void insert(Comparable11 x)
Insert into the priority queue. Duplicates are allowed.

Parameters:
x - the item to insert.
o addItem 
 public PairNode addItem(Comparable11 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 Comparable11 findMin() throws Underflow
Find the smallest item in the priority queue.

Returns:
the smallest item.
Throws: Underflow
if the priority queue is empty.
o deleteMin 
 public Comparable11 deleteMin() throws Underflow
Remove the smallest item from the priority queue.

Throws: Underflow
if the priority queue is empty.
o decreaseKey 
 public void decreaseKey(PairNode p,
                         Comparable11 newVal) throws IllegalValue
Change the value of the item stored in the pairing heap.

Parameters:
p - any node returned by addItem.
newVal - the new value, which must be smaller than the currently stored value.
Throws: IllegalValue
if newVal is larger 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 toss 
 public void toss(Comparable11 x)
Insert into the priority queue, without maintaining heap order. Duplicates are allowed.

Parameters:
x - the item to insert.
o validate 
 public void validate()

All Packages  Class Hierarchy  This Package  Previous  Next  Index