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. //end#fragment HeapPriorityQueue

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	HeapPriorityQueue.MyEntry<K,V> Inner class for heap entries.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Comparator<K>	comp
protected CompleteBinaryTree<Entry<K,V>>	heap

Constructor Summary

Constructors

Constructor and Description
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

Modifier and Type	Method and Description
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(java.util.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
java.lang.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 java.util.Comparator<K> comp

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

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 java.lang.String toString()

Text visualization for debugging purposes

Overrides:

toString in class java.lang.Object