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 java.lang.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.

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

Constructor Summary

HeapPriorityQueue()
Creates an empty heap with the default comparator

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

Method Summary

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(java.util.Comparator<K> c) Sets the comparator used for comparing items in the heap.
int	size() Returns the size of the heap
java.lang.String	toString() Text visualization for debugging purposes

Methods inherited from class java.lang.Object

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

Constructor Detail

HeapPriorityQueue

public HeapPriorityQueue()

Creates an empty heap with the default comparator

HeapPriorityQueue

public HeapPriorityQueue(java.util.Comparator<K> c)

Creates an empty heap with the given comparator

Method Detail

setComparator

public void setComparator(java.util.Comparator<K> c)
                   throws java.lang.IllegalStateException

Sets the comparator used for comparing items in the heap.

Throws:

java.lang.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

toString

public java.lang.String toString()

Text visualization for debugging purposes

Overrides:

toString in class java.lang.Object