Opus5
Class BinaryHeap

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.BinaryHeap

All Implemented Interfaces:

Comparable, Container, PriorityQueue

public class BinaryHeap

extends AbstractContainer

implements PriorityQueue

A priority queue implemented as a binary heap.

Version:

$Id: BinaryHeap.java,v 3.2 1998/07/28 02:24:04 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Field Summary

protected Comparable[]

array The heap.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.PriorityQueue

copyright

Constructor Summary

BinaryHeap(int length)
Constructs a BinaryHeap with the specified length.

Method Summary

void	accept(Visitor visitor) Accepts the specified visitor and makes it visit all the objects in this heap.
protected int	compareTo(Comparable arg) Compares this heap with the specified comparable object.
Comparable	dequeueMin() Dequeues and returns the "smallest" object in this heap.
void	enqueue(Comparable object) Enqueues the specified object.
Comparable	findMin() Returns the "smallest" object in this heap.
Enumeration	getEnumeration() Returns an enumeration that enumerates all the objects in this heap.
boolean	isFull() Tests whether this heap is full.
void	purge() Purges the heap, making it empty.

Methods inherited from class Opus5.AbstractContainer

getCount, hashCode, isEmpty, toString

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Container

getCount, isEmpty

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

array

protected Comparable[] array

The heap.

Constructor Detail

BinaryHeap

public BinaryHeap(int length)

Constructs a BinaryHeap with the specified length.

Parameters:

The - desired heap length.

Method Detail

purge

public void purge()

Purges the heap, making it empty.

Specified by:

purge in interface Container

enqueue

public void enqueue(Comparable object)

Enqueues the specified object.

Specified by:

enqueue in interface PriorityQueue

Parameters:

object - The object to enqueue.

Throws:

ContainerFullException - If the heap is full.

findMin

public Comparable findMin()

Returns the "smallest" object in this heap. The smallest element is the object in this heap that is less than or equal to all other objects in this heap.

Specified by:

findMin in interface PriorityQueue

Returns:

The "smallest" object in this heap.

Throws:

ContainerEmptyException - If the heap is empty.

dequeueMin

public Comparable dequeueMin()

Dequeues and returns the "smallest" object in this heap. The smallest element is the object in this heap that is less than or equal to all other objects in this heap.

Specified by:

dequeueMin in interface PriorityQueue

Returns:

The "smallest" object in this heap.

Throws:

ContainerEmptyException - If the heap is empty.

isFull

public boolean isFull()

Tests whether this heap is full.

Specified by:

isFull in interface Container

Overrides:

isFull in class AbstractContainer

Returns:

True if this heap is full; false otherwise.

accept

public void accept(Visitor visitor)

Accepts the specified visitor and makes it visit all the objects in this heap.

Specified by:

accept in interface Container

Overrides:

accept in class AbstractContainer

Parameters:

visitor - The visitor to accept.

getEnumeration

public Enumeration getEnumeration()

Returns an enumeration that enumerates all the objects in this heap.

Specified by:

getEnumeration in interface Container

Returns:

an enumeration that enumerates all the objects in this heap.

compareTo

protected int compareTo(Comparable arg)

Compares this heap with the specified comparable object. This method is not implemented.

Overrides:

compareTo in class AbstractObject

Parameters:

arg - The comparable object with which to compare this heap.

Throws:

MethodNotImplemented - Always.