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

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

All Implemented Interfaces:

PriorityQueue<AnyType>

public class BinaryHeap<AnyType extends java.lang.Comparable<? super AnyType>>
extends java.lang.Object
implements PriorityQueue<AnyType>

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

Nested Class Summary

Nested classes/interfaces inherited from interface weiss.nonstandard.PriorityQueue

PriorityQueue.Position<AnyType>

Constructor Summary

BinaryHeap()
Construct the binary heap.

BinaryHeap(AnyType[] items)
Construct the binary heap from an array.

Method Summary

void	decreaseKey(PriorityQueue.Position<AnyType> p, 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.
PriorityQueue.Position<AnyType>	insert(AnyType 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(AnyType[] items)

Construct the binary heap from an array.

Parameters:

items - the inital items in the binary heap.

Method Detail

insert

public PriorityQueue.Position<AnyType> insert(AnyType x)

Insert into the priority queue. Duplicates are allowed.

Specified by:

insert in interface PriorityQueue<AnyType extends java.lang.Comparable<? super AnyType>>

Parameters:

x - the item to insert.

Returns:

null, signifying that decreaseKey cannot be used.

decreaseKey

public void decreaseKey(PriorityQueue.Position<AnyType> p,
                        AnyType 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<AnyType extends java.lang.Comparable<? super AnyType>>

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.UnsupportedOperationException - because no Positions are returned by the insert method for BinaryHeap.

findMin

public AnyType findMin()

Find the smallest item in the priority queue.

Specified by:

findMin in interface PriorityQueue<AnyType extends java.lang.Comparable<? super AnyType>>

Returns:

the smallest item.

Throws:

UnderflowException - if empty.

deleteMin

public AnyType deleteMin()

Remove the smallest item from the priority queue.

Specified by:

deleteMin in interface PriorityQueue<AnyType extends java.lang.Comparable<? super AnyType>>

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<AnyType extends java.lang.Comparable<? super AnyType>>

Returns:

true if empty, false otherwise.

size

public int size()

Returns size.

Specified by:

size in interface PriorityQueue<AnyType extends java.lang.Comparable<? super AnyType>>

Returns:

current size.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

Specified by:

makeEmpty in interface PriorityQueue<AnyType extends java.lang.Comparable<? super AnyType>>

main

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