    All Packages  Class Hierarchy  This Package  Previous  Next  Index

# Class DataStructures.PairHeap

    java.lang.Object
        |
        +----DataStructures.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.

See Also:
  PairNode

##

PairHeap()
  Construct the pairing heap.

##

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

##

PairHeap

    public PairHeap()

  Construct the pairing heap.

##

insert

    public void insert(Comparable x)

  Insert into the priority queue. Duplicates are allowed.

  Parameters:
    x - the item to insert.

addItem

    public PairNode addItem(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() throws Underflow

  Find the smallest item in the priority queue.

  Returns:
    the smallest item.
  Throws: Underflow
    if the priority queue is empty.

deleteMin

    public Comparable deleteMin() throws Underflow

  Remove the smallest item from the priority queue.

  Throws: Underflow
    if the priority queue is empty.

decreaseKey

    public void decreaseKey(PairNode p,
                            Comparable 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.

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(String[] args)

    All Packages  Class Hierarchy  This Package  Previous  Next  Index