Package minpq

Class OptimizedHeapMinPQ<T>

java.lang.Object

minpq.OptimizedHeapMinPQ<T>

Type Parameters:

T - the type of elements in this priority queue.

All Implemented Interfaces:

ExtrinsicMinPQ<T>

public class OptimizedHeapMinPQ<T>
extends Object
implements ExtrinsicMinPQ<T>

Optimized binary heap implementation of the ExtrinsicMinPQ interface.

See Also:

ExtrinsicMinPQ

Field Summary

Fields

Modifier and Type	Field	Description
private List<PriorityNode<T>>	items	List of PriorityNode objects representing the heap of item-priority pairs.
private Map<T,Integer>	itemToIndex	Map of each item to its associated index in the items heap.
private int	size	The number of elements in the heap.

Constructor Summary

Constructors

Constructor	Description
OptimizedHeapMinPQ()	Constructs an empty instance.

Method Summary

Modifier and Type	Method	Description
void	add(T item, double priority)	Adds an item with the given priority value.
void	changePriority(T item, double priority)	Updates the given items' associated priority value.
boolean	contains(T item)	Returns true if the given item is in this priority queue.
T	peekMin()	Returns the item with the minimum priority value.
T	removeMin()	Returns and removes the item with the minimum priority value.
int	size()	Returns the number of items in this priority queue.

Methods inherited from class java.lang.Object

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

Methods inherited from interface minpq.ExtrinsicMinPQ

isEmpty

Field Detail

items

private final List<PriorityNode<T>> items

List of PriorityNode objects representing the heap of item-priority pairs.

itemToIndex

private final Map<T,Integer> itemToIndex

Map of each item to its associated index in the items heap.

size

private int size

The number of elements in the heap.

Constructor Detail

OptimizedHeapMinPQ

public OptimizedHeapMinPQ()

Constructs an empty instance.

Method Detail

add

public void add(T item,
                double priority)

Description copied from interface: ExtrinsicMinPQ

Adds an item with the given priority value.

Specified by:

add in interface ExtrinsicMinPQ<T>

Parameters:

item - the element to add.

priority - the priority value for the item.

contains

public boolean contains(T item)

Description copied from interface: ExtrinsicMinPQ

Returns true if the given item is in this priority queue.

Specified by:

contains in interface ExtrinsicMinPQ<T>

Parameters:

item - element to be checked for containment.

Returns:

true if the given item is in this priority queue.

peekMin

public T peekMin()

Description copied from interface: ExtrinsicMinPQ

Returns the item with the minimum priority value.

Specified by:

peekMin in interface ExtrinsicMinPQ<T>

Returns:

the item with the minimum priority value.

removeMin

public T removeMin()

Description copied from interface: ExtrinsicMinPQ

Returns and removes the item with the minimum priority value.

Specified by:

removeMin in interface ExtrinsicMinPQ<T>

Returns:

the item with the minimum priority value.

changePriority

public void changePriority(T item,
                           double priority)

Description copied from interface: ExtrinsicMinPQ

Updates the given items' associated priority value.

Specified by:

changePriority in interface ExtrinsicMinPQ<T>

Parameters:

item - the element whose associated priority value should be modified.

priority - the updated priority value.

size

public int size()

Description copied from interface: ExtrinsicMinPQ

Returns the number of items in this priority queue.

Specified by:

size in interface ExtrinsicMinPQ<T>

Returns:

the number of elements in this priority queue.