net.datastructures
Class HeapPriorityQueue

java.lang.Object
  net.datastructures.HeapPriorityQueue

All Implemented Interfaces:

PriorityQueue

Direct Known Subclasses:

HeapAdaptablePriorityQueue

public class HeapPriorityQueue

extends Object

implements PriorityQueue

Realization of a priority queue by means of a heap. The heap is built upon a vector-based complete binary tree.

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

Nested Class Summary

protected static class	HeapPriorityQueue.DefaultComparator Inner class for a comparator that uses the natural ordering of keys.
protected static class	HeapPriorityQueue.MyEntry Inner class for heap entries.

Field Summary

protected Comparator	comp
protected CompleteBinaryTree	T

Constructor Summary

HeapPriorityQueue()
Creates an empty heap with the default comparator.

HeapPriorityQueue(Comparator c)
Creates an empty heap with the given comparator.

Method Summary

protected void	checkKey(Object key) Determines whether a given key is valid.
protected void	downHeap(Position r) Performs down-heap bubbling.
protected Entry	entry(Position p) Returns the entry stored at a heap node.
Entry	insert(Object k, Object x) Inserts a key-value pair and return the entry created.
boolean	isEmpty() Returns whether the heap is empty.
protected Object	key(Position p) Returns the key stored at a heap node.
Entry	min() Returns but does not remove an entry with minimum key.
Entry	removeMin() Removes and returns an entry with minimum key.
void	setComparator(Comparator c) Sets the comparator used for comparing items in the heap.
int	size() Returns the size of the heap.
protected void	swapElements(Position x, Position y) Swaps the elements of the two positions.
String	toString() Text visualization for debugging purposes
protected void	upHeap(Position v) Performs up-heap bubbling.

Methods inherited from class java.lang.Object

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

Field Detail

T

protected CompleteBinaryTree T

comp

protected Comparator comp

Constructor Detail

HeapPriorityQueue

public HeapPriorityQueue()

Creates an empty heap with the default comparator.

HeapPriorityQueue

public HeapPriorityQueue(Comparator c)

Creates an empty heap with the given comparator.

Method Detail

setComparator

public void setComparator(Comparator 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

isEmpty

public boolean isEmpty()

Returns whether the heap is empty.

Specified by:

isEmpty in interface PriorityQueue

min

public Entry min()
          throws EmptyPriorityQueueException

Returns but does not remove an entry with minimum key.

Specified by:

min in interface PriorityQueue

Throws:

EmptyPriorityQueueException

insert

public Entry insert(Object k,
                    Object x)
             throws InvalidKeyException

Inserts a key-value pair and return the entry created.

Specified by:

insert in interface PriorityQueue

Throws:

InvalidKeyException

removeMin

public Entry removeMin()
                throws EmptyPriorityQueueException

Removes and returns an entry with minimum key.

Specified by:

removeMin in interface PriorityQueue

Throws:

EmptyPriorityQueueException

entry

protected Entry entry(Position p)

Returns the entry stored at a heap node.

key

protected Object key(Position p)

Returns the key stored at a heap node.

checkKey

protected void checkKey(Object key)
                 throws InvalidKeyException

Determines whether a given key is valid.

Throws:

InvalidKeyException

upHeap

protected void upHeap(Position v)

Performs up-heap bubbling.

downHeap

protected void downHeap(Position r)

Performs down-heap bubbling.

swapElements

protected void swapElements(Position x,
                            Position y)

Swaps the elements of the two positions.

toString

public String toString()

Text visualization for debugging purposes