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)