net.datastructures
Class HeapPriorityQueue<K,V>

java.lang.Object
  net.datastructures.HeapPriorityQueue<K,V>

All Implemented Interfaces:

PriorityQueue<K,V>

Direct Known Subclasses:

HeapAdaptablePriorityQueue

public class HeapPriorityQueue<K,V>
extends Object
implements PriorityQueue<K,V>

Realization of a priority queue by means of a heap. A complete binary tree realized by means of an array list is used to represent the heap. //end#fragment HeapPriorityQueue

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore //begin#fragment HeapPriorityQueue

Nested Class Summary

protected static class

HeapPriorityQueue.MyEntry<K,V> Inner class for heap entries.

Field Summary

protected Comparator<K>	comp
protected CompleteBinaryTree<Entry<K,V>>	heap

Constructor Summary

HeapPriorityQueue()
Creates an empty heap with the default comparator

HeapPriorityQueue(Comparator<K> c)
Creates an empty heap with the given comparator

Method Summary

protected void	checkKey(K key) Determines whether a given key is valid
protected void	downHeap(Position<Entry<K,V>> r) Performs down-heap bubbling
Entry<K,V>	insert(K k, V x) 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>	removeMin() Removes and returns an entry with minimum key
void	setComparator(Comparator<K> c) Sets the comparator used for comparing items in the heap.
int	size() Returns the size of the heap
protected void	swap(Position<Entry<K,V>> x, Position<Entry<K,V>> y) Swaps the entries of the two given positions
String	toString() Text visualization for debugging purposes
protected void	upHeap(Position<Entry<K,V>> v) Performs up-heap bubbling

Methods inherited from class java.lang.Object

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

Field Detail

heap

protected CompleteBinaryTree<Entry<K,V>> heap

comp

protected Comparator<K> comp

Constructor Detail

HeapPriorityQueue

public HeapPriorityQueue()

Creates an empty heap with the default comparator

HeapPriorityQueue

public HeapPriorityQueue(Comparator<K> c)

Creates an empty heap with the given comparator

Method Detail

setComparator

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

Sets the comparator used for comparing items in the heap.

Throws:

IllegalStateException - if priority queue is not empty

size

public int size()

Returns the size of the heap

Specified by:

size in interface PriorityQueue<K,V>

isEmpty

public boolean isEmpty()

Returns whether the heap is empty

Specified by:

isEmpty in interface PriorityQueue<K,V>

min

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

Returns but does not remove an entry with minimum key

Specified by:

min in interface PriorityQueue<K,V>

Throws:

EmptyPriorityQueueException

insert

public Entry<K,V> insert(K k,
                         V x)
                  throws InvalidKeyException

Inserts a key-value pair and returns the entry created

Specified by:

insert in interface PriorityQueue<K,V>

Throws:

InvalidKeyException

removeMin

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

Removes and returns an entry with minimum key

Specified by:

removeMin in interface PriorityQueue<K,V>

Throws:

EmptyPriorityQueueException

checkKey

protected void checkKey(K key)
                 throws InvalidKeyException

Determines whether a given key is valid

Throws:

InvalidKeyException

upHeap

protected void upHeap(Position<Entry<K,V>> v)

Performs up-heap bubbling

downHeap

protected void downHeap(Position<Entry<K,V>> r)

Performs down-heap bubbling

swap

protected void swap(Position<Entry<K,V>> x,
                    Position<Entry<K,V>> y)

Swaps the entries of the two given positions

toString

public String toString()

Text visualization for debugging purposes

Overrides:

toString in class Object