structure
Class VectorHeap

java.lang.Object
  |
  +--structure.VectorHeap

All Implemented Interfaces:

PriorityQueue

public class VectorHeap

extends Object

implements PriorityQueue

This class implements a priority queue based on a traditional array-based heap. Most heap operations, including insert and remove, execute in logarithmic time, but the minimum element can be returned in constant time.

Example usage:

To print out a list of programmers sorted by age we could use the following:

 public static void main(String[] argv){
	//initialize a new fib heap
	VectorHeap programmers = new VectorHeap();

	//add programmers and their ages to heap
	//ages current of 7/22/2002
	//add programmers and their ages to heap
	//ages current of 7/22/2002
        programmers.add(new ComparableAssociation(new Integer(22), "Evan"));
	programmers.add(new ComparableAssociation(new Integer(19), "Chris"));
	programmers.add(new ComparableAssociation(new Integer(20), "Shimon"));
	programmers.add(new ComparableAssociation(new Integer(21), "Diane"));
	programmers.add(new ComparableAssociation(new Integer(21), "Lida"));	
	programmers.add(new ComparableAssociation(new Integer(20), "Rob"));	
	programmers.add(new ComparableAssociation(new Integer(20), "Sean"));	

	//print out programmers 
	while(!programmers.isEmpty()){
	    ComparableAssociation p = (ComparableAssociation)programmers.remove();
	    System.out.println(p.getValue() + " is " + p.getKey() + " years old.");
	}
 }
 

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(Comparable value) Add a value to the priority queue.
void	clear() Remove all the elements from the queue.
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.
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.
String	toString() Construct a string representation of the heap.

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, 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

VectorHeap

public VectorHeap(Vector v)

Construct 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

Precondition:

0 <= i < size

Postcondition:

returns parent of node at location i

Returns:

parent of node at i

left

protected static int left(int i)

Returns left child index.

Parameters:

i - a node index

Precondition:

0 <= i < size

Postcondition:

returns index of left child of node at location i

Returns:

left child of node at i

right

protected static int right(int i)

Returns right child index.

Parameters:

i - a node index

Precondition:

0 <= i < size

Postcondition:

returns index of right child of node at location i

Returns:

right child of node at i

getFirst

public Comparable getFirst()

Fetch lowest valued (highest priority) item from queue.

Specified by:

getFirst in interface PriorityQueue

Precondition:

!isEmpty()

Postcondition:

returns the minimum value in priority queue

Returns:

The smallest value from queue.

remove

public Comparable remove()

Returns the minimum value from the queue.

Specified by:

remove in interface PriorityQueue

Precondition:

!isEmpty()

Postcondition:

returns and removes minimum value from queue

Returns:

The minimum value in the queue.

add

public void add(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

Postcondition:

returns true iff no elements are in queue

Returns:

True if the queue is empty.

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

Postcondition:

returns number of elements within queue

Returns:

The number of elements within the 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 String toString()

Construct a string representation of the heap.

Overrides:

toString in class Object

Postcondition:

returns string representation of heap

Returns:

The string representing the heap.