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. 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(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


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
Returns:
parent of node at i

left

protected static int left(int i)
Returns left child index.

Parameters:
i - a node index
Returns:
left child of node at i

right

protected static int right(int i)
Returns right child index.

Parameters:
i - a node index
Returns:
right child of node at 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.

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.

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.

isEmpty

public boolean isEmpty()
Determine if the queue is empty.

Specified by:
isEmpty in interface PriorityQueue
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.

pushDownRoot

protected void pushDownRoot(int root)
Moves node downward, into appropriate position within subheap.

Parameters:
root - Index of the root of the subheap.

size

public int size()
Determine the size of the queue.

Specified by:
size in interface PriorityQueue
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

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.