structure
Class VectorHeap

java.lang.Object
  structure.VectorHeap

All Implemented Interfaces:

PriorityQueue

public class VectorHeap
extends java.lang.Object
implements PriorityQueue

This class implements a priority queue based on a traditional array-based heap.

Field Summary

protected Vector

data The data, kept in heap order.

Constructor Summary

VectorHeap()
Construct a new priority queue

VectorHeap(Vector v)
Construct a new priority queue from an unordered vector

Method Summary

void	add(java.lang.Comparable value) Add a value to the priority queue.
void	clear() Remove all the elements from the queue.
java.lang.Comparable	getFirst() Fetch lowest valued (highest priority) item from queue.
boolean	isEmpty() Determine if the queue is empty.
protected static int	left(int i) Returns left child index.
protected static int	parent(int i) Returns parent index
protected void	percolateUp(int leaf) Moves node upward to appropriate position within heap.
protected void	pushDownRoot(int root) Moves node downward, into appropriate position within subheap.
java.lang.Comparable	remove() Returns the minimum value from the queue.
protected static int	right(int i) Returns right child index.
int	size() Determine the size of the queue.
java.lang.String	toString() Construct a string representation of the heap.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

data

protected Vector data

The data, kept in heap order.

Constructor Detail

VectorHeap

public VectorHeap()

Construct a new priority queue

Postcondition:

constructs a new priority queue

VectorHeap

public VectorHeap(Vector v)

Construct a new priority queue from an unordered vector

Postcondition:

constructs a new priority queue from an unordered vector

Method Detail

parent

protected static int parent(int i)

Returns parent index

Parameters:

i - a node index

Returns:

parent of node at i

Precondition:

0 <= i < size

Postcondition:

returns parent of node at location i

left

protected static int left(int i)

Returns left child index.

Parameters:

i - a node index

Returns:

left child of node at i

Precondition:

0 <= i < size

Postcondition:

returns index of left child of node at location i

right

protected static int right(int i)

Returns right child index.

Parameters:

i - a node index

Returns:

right child of node at i

Precondition:

0 <= i < size

Postcondition:

returns index of right child of node at location i

getFirst

public java.lang.Comparable getFirst()

Fetch lowest valued (highest priority) item from queue.

Specified by:

getFirst in interface PriorityQueue

Returns:

The smallest value from queue.

Precondition:

!isEmpty()

Postcondition:

returns the minimum value in priority queue

remove

public java.lang.Comparable remove()

Returns the minimum value from the queue.

Specified by:

remove in interface PriorityQueue

Returns:

The minimum value in the queue.

Precondition:

!isEmpty()

Postcondition:

returns and removes minimum value from queue

add

public void add(java.lang.Comparable value)

Add a value to the priority queue.

Specified by:

add in interface PriorityQueue

Parameters:

value - The value to be added.

Precondition:

value is non-null comparable

Postcondition:

value is added to priority queue

isEmpty

public boolean isEmpty()

Determine if the queue is empty.

Specified by:

isEmpty in interface PriorityQueue

Returns:

True if the queue is empty.

Postcondition:

returns true iff no elements are in queue

percolateUp

protected void percolateUp(int leaf)

Moves node upward to appropriate position within heap.

Parameters:

leaf - Index of the node in the heap.

Precondition:

0 <= leaf < size

Postcondition:

moves node at index leaf up to appropriate position

pushDownRoot

protected void pushDownRoot(int root)

Moves node downward, into appropriate position within subheap.

Parameters:

root - Index of the root of the subheap.

Precondition:

0 <= root < size

Postcondition:

moves node at index root down to appropriate position in subtree

size

public int size()

Determine the size of the queue.

Specified by:

size in interface PriorityQueue

Returns:

The number of elements within the queue.

Postcondition:

returns number of elements within queue

clear

public void clear()

Remove all the elements from the queue.

Specified by:

clear in interface PriorityQueue

Postcondition:

removes all elements from queue

toString

public java.lang.String toString()

Construct a string representation of the heap.

Overrides:

toString in class java.lang.Object

Returns:

The string representing the heap.

Postcondition:

returns string representation of heap