structure5
Class VectorHeap<E extends java.lang.Comparable<E>>

java.lang.Object
  structure5.VectorHeap<E>

All Implemented Interfaces:

PriorityQueue<E>

public class VectorHeap<E extends java.lang.Comparable<E>>
extends java.lang.Object
implements PriorityQueue<E>

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<E>

data The data, kept in heap order.

Constructor Summary

VectorHeap()
Construct a new priority queue

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

Method Summary

void	add(E value) Add a value to the priority queue.
void	clear() Remove all the elements from the queue.
E	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.
E	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<E extends java.lang.Comparable<E>> 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<E> 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 E getFirst()

Fetch lowest valued (highest priority) item from queue.

Specified by:

getFirst in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The smallest value from queue.

Precondition:

!isEmpty()

Postcondition:

returns the minimum value in priority queue

remove

public E remove()

Returns the minimum value from the queue.

Specified by:

remove in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The minimum value in the queue.

Precondition:

!isEmpty()

Postcondition:

returns and removes minimum value from queue

add

public void add(E value)

Add a value to the priority queue.

Specified by:

add in interface PriorityQueue<E extends java.lang.Comparable<E>>

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<E extends java.lang.Comparable<E>>

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<E extends java.lang.Comparable<E>>

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<E extends java.lang.Comparable<E>>

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