heap
Class MyHeap<K,V>

java.lang.Object
  heap.MyHeap<K,V>

All Implemented Interfaces:

AdaptablePriorityQueue<K,V>, PriorityQueue<K,V>, HeapWrapper<K,V>

public class MyHeap<K,V>
extends Object
implements AdaptablePriorityQueue<K,V>, HeapWrapper<K,V>

An implementation of an adaptable priority queue by means of a heap. Be certain that your running times match those specified in the program documentation, and remember that the running time of a "called" method sets the minimum running time of the "calling" method. Feel free to add additional comments.

Constructor Summary

MyHeap(Comparator<K> comparator)
Creates an empty heap with the given comparator.

Method Summary

CompleteBinaryTree<Entry<K,V>>	getTree() Returns a CompleteBinaryTree that will allow the visualizer access to private members, shattering encapsulation, but allowing visualization of the heap.
Entry<K,V>	insert(K key, V value) Inserts a key-value pair and returns the entry created.
boolean	isEmpty() Returns whether the heap is empty.
Entry<K,V>	min() Returns but does not remove an entry with minimum key.
Entry<K,V>	remove(Entry<K,V> entry) Removes and returns the given entry from the heap.
Entry<K,V>	removeMin() Removes and returns an entry with minimum key.
K	replaceKey(Entry<K,V> entry, K key) Replaces the key of the given entry.
V	replaceValue(Entry<K,V> entry, V value) Replaces the value of the given entry.
void	setComparator(Comparator<K> comparator) Sets the comparator used for comparing items in the heap.
int	size() Returns the size of the heap.

Methods inherited from class java.lang.Object

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

Constructor Detail

MyHeap

public MyHeap(Comparator<K> comparator)

Creates an empty heap with the given comparator.

Parameters:

comparator - the comparator to be used for heap keys

Method Detail

setComparator

public void setComparator(Comparator<K> comparator)
                   throws IllegalStateException

Sets the comparator used for comparing items in the heap.

Parameters:

comparator - the comparator to be used for heap keys

Throws:

IllegalStateException - if priority queue is not empty

getTree

public CompleteBinaryTree<Entry<K,V>> getTree()

Returns a CompleteBinaryTree that will allow the visualizer access to private members, shattering encapsulation, but allowing visualization of the heap. This is the only method needed to satisfy HeapWrapper interface implementation.

Specified by:

getTree in interface HeapWrapper<K,V>

Returns:

the underlying binary tree on which the heap is based

size

public int size()

Returns the size of the heap. This method must run in O(1) time.

Specified by:

size in interface PriorityQueue<K,V>

Returns:

an int representing the number of entries stored

isEmpty

public boolean isEmpty()

Returns whether the heap is empty. This method must run in O(1) time.

Specified by:

isEmpty in interface PriorityQueue<K,V>

Returns:

true if the heap is empty; false otherwise

min

public Entry<K,V> min()
               throws EmptyPriorityQueueException

Returns but does not remove an entry with minimum key. This method must run in O(1) time.

Specified by:

min in interface PriorityQueue<K,V>

Returns:

the entry with the minimum key in the heap

Throws:

EmptyPriorityQueueException - if the heap is empty

insert

public Entry<K,V> insert(K key,
                         V value)
                  throws InvalidKeyException

Inserts a key-value pair and returns the entry created. This method must run in O(log n) time.

Specified by:

insert in interface PriorityQueue<K,V>

Parameters:

key - to be used as the key the heap is sorting with

value - stored with the associated key in the heap

Returns:

the entry created using the key/value parameters

Throws:

InvalidKeyException - if the key is not suitable for this heap

removeMin

public Entry<K,V> removeMin()
                     throws EmptyPriorityQueueException

Removes and returns an entry with minimum key. This method must run in O(log n) time.

Specified by:

removeMin in interface PriorityQueue<K,V>

Returns:

the entry with the with the minimum key, now removed

Throws:

EmptyPriorityQueueException - if the heap is empty

remove

public Entry<K,V> remove(Entry<K,V> entry)
                  throws InvalidEntryException

Removes and returns the given entry from the heap. This method must run in O(log n) time.

Specified by:

remove in interface AdaptablePriorityQueue<K,V>

Parameters:

entry - to be removed from the heap

Returns:

the entry specified for removal by the parameter

Throws:

InvalidEntryException - if the entry cannot be removed from this heap

replaceKey

public K replaceKey(Entry<K,V> entry,
                    K key)
             throws InvalidEntryException

Replaces the key of the given entry. This method must run in O(log n) time.

Specified by:

replaceKey in interface AdaptablePriorityQueue<K,V>

Parameters:

entry - within which the key will be replaced

key - to replace the existing key in the entry

Returns:

the old key formerly associated with the entry

Throws:

InvalidEntryException - if the entry cannot have its key replaced

replaceValue

public V replaceValue(Entry<K,V> entry,
                      V value)
               throws InvalidEntryException

Replaces the value of the given entry. This method must run in O(1) time.

Specified by:

replaceValue in interface AdaptablePriorityQueue<K,V>

Parameters:

entry - within which the value will be replaced

value - to replace the existing value in the entry

Returns:

the old value formerly associated with the entry

Throws:

InvalidEntryException - if the entry cannot have its value replaced