: Interface PriorityQueue

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

## weiss.nonstandard
Interface PriorityQueue

All Known Implementing Classes:
  PairingHeap, BinaryHeap

public interface PriorityQueue

PriorityQueue interface. Some priority queues may support a decreaseKey operation, but this is considered an advanced operation. If so, a Position is returned by insert. Note that all "matching" is based on the compareTo method.

Inner Class Summary
`static interface` | `PriorityQueue.Position` The Position interface represents a type that can be used for the decreaseKey operation.

Method Summary
`void` | `decreaseKey(PriorityQueue.Position p, java.lang.Comparable newVal)` Change the value of the item stored in the pairing heap.
`java.lang.Comparable` | `deleteMin()` Remove the smallest item from the priority queue.
`java.lang.Comparable` | `findMin()` Find the smallest item in the priority queue.
`PriorityQueue.Position` | `insert(java.lang.Comparable x)` Insert into the priority queue, maintaining heap order.
`boolean` | `isEmpty()` Test if the priority queue is logically empty.
`void` | `makeEmpty()` Make the priority queue logically empty.
`int` | `size()` Returns the size.

Method Detail

### insert

    public PriorityQueue.Position insert(java.lang.Comparable x)

  Insert into the priority queue, maintaining heap order. Duplicates are allowed.
  Parameters:
    `x` - the item to insert.
  Returns:
    may return a Position useful for decreaseKey.

### findMin

    public java.lang.Comparable findMin()

  Find the smallest item in the priority queue.
  Returns:
    the smallest item.
  Throws:
    `UnderflowException` - if empty.

### deleteMin

    public java.lang.Comparable deleteMin()

  Remove the smallest item from the priority queue.
  Returns:
    the smallest item.
  Throws:
    `UnderflowException` - if empty.

### 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.

### size

    public int size()

  Returns the size.
  Returns:
    current size.

### decreaseKey

    public void decreaseKey(PriorityQueue.Position p,
                            java.lang.Comparable newVal)

  Change the value of the item stored in the pairing heap. This is considered an advanced operation and might not be supported by all priority queues. A priority queue will signal its intention to not support decreaseKey by having insert return null consistently.
  Parameters:
    `p` - any non-null Position returned by insert.
    `newVal` - the new value, which must be smaller than the currently stored value.
  Throws:
    `java.lang.IllegalArgumentException` - if p invalid

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