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)