org.mathIT.graphs

Class PriorityQueue<V extends Vertible<V>>

java.lang.Object

org.mathIT.graphs.PriorityQueue<V>

Type Parameters:

V - the type of the vertices of the graph

public class PriorityQueue<V extends Vertible<V>>
extends Object

This class represents a priority queue for an array list of vertices. The priority queue is ordered as a minimum heap such that its root is guaranteed to be the vertex with the minimum key. Usually, the key is the distance to a given start vertex in a weighted graph. The priority queue class is used in the Dijkstra algorithm.

Version:

1.1

Author:

Andreas de Vries

See Also:

Vertible, WeightedGraph.dijkstra(int)

Constructor Summary

Constructors

Constructor and Description
PriorityQueue(V[] vertices) Creates a priority queue containing the input vertices.

Method Summary

Modifier and Type	Method and Description
boolean	decreaseKey(V v, double d) Decreases the key of the specified element v to the value d.
V	extractMin() Returns the minimum of this priority queue and deletes it from the queue.
V	getRoot() Returns the root of the heap representing this priority queue.
int	size() Returns the number of elements in this priority queue.
String	toString() Returns a string representationj of this priority queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

PriorityQueue

public PriorityQueue(V[] vertices)

Creates a priority queue containing the input vertices.

Parameters:

vertices - an array of vertices

Method Detail

size

public int size()

Returns the number of elements in this priority queue.

Returns:

the number of elements in this priority queue.

getRoot

public V getRoot()

Returns the root of the heap representing this priority queue. In fact, the root is the element with the minimum key.

Returns:

the root number of elements in this priority queue.

extractMin

public V extractMin()

Returns the minimum of this priority queue and deletes it from the queue.

Returns:

the minimum vertex of this priority queue

decreaseKey

public boolean decreaseKey(V v,
                           double d)

Decreases the key of the specified element v to the value d. The element remains unmodified if the new key is not less than the current key value. In the Dijkstra algorithm, the key is the current minimum distance of the vertex to a specified start vertex.

Parameters:

v - the vertex whose key is to be decreased

d - the new value of the key

Returns:

true if and only if the new value d is less than the current key value

toString

public String toString()

Returns a string representationj of this priority queue.

Overrides:

toString in class Object

Returns:

a string representationj of this priority queue