PairingHeap
Keywords: weiss.nonstandard.PairingHeap class

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## weiss.nonstandard
Class PairingHeap<AnyType extends java.lang.Comparable<? super AnyType>>

    java.lang.Object
      weiss.nonstandard.PairingHeap<AnyType>

    public class PairingHeap<AnyType extends java.lang.Comparable<? super AnyType>>

extends java.lang.Object

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

See Also:
  `PriorityQueue.Position`

Nested Class Summary
`static interface` | `PairingHeap.Position<AnyType>` The Position interface represents a type that can be used for the decreaseKey operation.

Constructor Summary
`PairingHeap()` Construct the pairing heap.

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

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

  Find the smallest item in the priority queue.

  Returns:
    the smallest item.
  Throws:
    `UnderflowException` - if pairing heap is empty.

### deleteMin

    public AnyType deleteMin()

  Remove the smallest item from the priority queue.

  Returns:
    the smallest item.
  Throws:
    `UnderflowException` - if pairing heap is empty.

### decreaseKey

    public void decreaseKey(PairingHeap.Position<AnyType> pos,
                            AnyType newVal)

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

  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.

  Returns:
    true if empty, false otherwise.

### size

    public int size()

  Returns number of items stored in the priority queue.

  Returns:
    size of the priority queue.

### makeEmpty

    public void makeEmpty()

  Make the priority queue logically empty.

### main

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

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD