: Class BinaryHeap

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
Class BinaryHeap

    java.lang.Object
      |
      +--weiss.nonstandard.BinaryHeap

All Implemented Interfaces:
  PriorityQueue

public class BinaryHeap
extends java.lang.Object
implements PriorityQueue

Implements a binary heap. Note that all "matching" is based on the compareTo method.

Inner classes inherited from class weiss.nonstandard.PriorityQueue
`PriorityQueue.Position`

Constructor Summary
`BinaryHeap()` Construct the binary heap.
`BinaryHeap(java.lang.Comparable[] items)` Construct the binary heap from an array.

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.
`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 size.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### BinaryHeap

    public BinaryHeap()

  Construct the binary heap.

### BinaryHeap

    public BinaryHeap(java.lang.Comparable[] items)

  Construct the binary heap from an array.
  Parameters:
    `items` - the inital items in the binary heap.

Method Detail

### insert

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

  Insert into the priority queue. Duplicates are allowed.
  Specified by:
    `insert` in interface `PriorityQueue`
  Parameters:
    `x` - the item to insert.
  Returns:
    null, signifying that decreaseKey cannot be used.

### decreaseKey

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

  Description copied from interface: `PriorityQueue`
  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.
  Specified by:
    `decreaseKey` in interface `PriorityQueue`
  Throws:
    `java.lang.IllegalArgumentException` - because no Positions are returned by the insert method for BinaryHeap.

### findMin

    public java.lang.Comparable findMin()

  Find the smallest item in the priority queue.
  Specified by:
    `findMin` in interface `PriorityQueue`
  Returns:
    the smallest item.
  Throws:
    `UnderflowException` - if empty.

### deleteMin

    public java.lang.Comparable deleteMin()

  Remove the smallest item from the priority queue.
  Specified by:
    `deleteMin` in interface `PriorityQueue`
  Returns:
    the smallest item.
  Throws:
    `UnderflowException` - if empty.

### isEmpty

    public boolean isEmpty()

  Test if the priority queue is logically empty.
  Specified by:
    `isEmpty` in interface `PriorityQueue`
  Returns:
    true if empty, false otherwise.

### size

    public int size()

  Returns size.
  Specified by:
    `size` in interface `PriorityQueue`
  Returns:
    current size.

### makeEmpty

    public void makeEmpty()

  Make the priority queue logically empty.
  Specified by:
    `makeEmpty` in interface `PriorityQueue`

### main

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

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