structure
Class VectorHeap<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

java.lang.Object
  structure.VectorHeap<ELTTYPE>

All Implemented Interfaces:

PriorityQueue<ELTTYPE>

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

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.");
        }
 }
 

Constructor Summary

VectorHeap()
Construct a new priority queue

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

Method Summary

void	add(ELTTYPE value) Add a value to the priority queue.
void	clear() Remove all the elements from the queue.
ELTTYPE	getFirst() Fetch lowest valued (highest priority) item from queue.
boolean	isEmpty() Determine if the queue is empty.
ELTTYPE	remove() Returns the minimum value from the queue.
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

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

VectorHeap

public VectorHeap()

Construct a new priority queue

Post:

constructs a new priority queue

VectorHeap

public VectorHeap(Vector<ELTTYPE> v)

Construct a new priority queue from an unordered vector

Post:

constructs a new priority queue from an unordered vector

Method Detail

getFirst

public ELTTYPE getFirst()

Fetch lowest valued (highest priority) item from queue.

Specified by:

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

Returns:

The smallest value from queue.

Pre:

!isEmpty()

Post:

returns the minimum value in priority queue

remove

public ELTTYPE remove()

Returns the minimum value from the queue.

Specified by:

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

Returns:

The minimum value in the queue.

Pre:

!isEmpty()

Post:

returns and removes minimum value from queue

add

public void add(ELTTYPE value)

Add a value to the priority queue.

Specified by:

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

Parameters:

value - The value to be added.

Pre:

value is non-null comparable

Post:

value is added to priority queue

isEmpty

public boolean isEmpty()

Determine if the queue is empty.

Specified by:

isEmpty in interface PriorityQueue<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Returns:

True if the queue is empty.

Post:

returns true iff no elements are in queue

size

public int size()

Determine the size of the queue.

Specified by:

size in interface PriorityQueue<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Returns:

The number of elements within the queue.

Post:

returns number of elements within queue

clear

public void clear()

Remove all the elements from the queue.

Specified by:

clear in interface PriorityQueue<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Post:

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.

Post:

returns string representation of heap