y.util.pq
Class BHeapDoubleNodePQ

java.lang.Object
  y.util.pq.BHeapDoubleNodePQ

All Implemented Interfaces:

DoubleNodePQ

public class BHeapDoubleNodePQ
extends java.lang.Object
implements DoubleNodePQ

This class implements a priority queue for nodes whose priority values are of type double.

The implementation is based on binary heaps.

Constructor Summary

BHeapDoubleNodePQ(Graph graph)
Creates an empty NodePQ for nodes contained in the given graph.

Method Summary

void	add(Node v, double value) Adds the given node with with given priority to this queue.
void	changePriority(Node v, double p) Changes the priority value of the given node.
void	clear() Makes this queue the empty queue.
boolean	contains(Node v) Returns whether or not the given node is contained in this queue.
void	decreasePriority(Node v, double priority) Decreases the priority value of the given node.
void	dispose() Does nothing.
Node	getMin() Returns the node with smallest priority in this queue.
double	getMinPriority() Returns the minimum priority value in this queue.
double	getPriority(Node v) Returns the current priority of the given node.
void	increasePriority(Node v, double priority) Increases the priority value of the given node.
boolean	isEmpty() Returns whether or not this queue is empty
void	remove(Node v) Removes the given node from this queue.
Node	removeMin() Removes the node with smallest priority from this queue.
int	size() Returns the number of nodes currently in this queue

Methods inherited from class java.lang.Object

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

Constructor Detail

BHeapDoubleNodePQ

public BHeapDoubleNodePQ(Graph graph)

Creates an empty NodePQ for nodes contained in the given graph. Neither the node set nor the indices of the nodes of the given graph may change while this queue is being used.

Method Detail

add

public void add(Node v,
                double value)

Adds the given node with with given priority to this queue.

Specified by:

add in interface DoubleNodePQ

Precondition:

!contains(v)

Complexity:

O(log(size()))

decreasePriority

public void decreasePriority(Node v,
                             double priority)

Decreases the priority value of the given node.

Specified by:

decreasePriority in interface DoubleNodePQ

Preconditions:

contains(v)

c.compare(p,getPriority(v)) < 0, where c is the corresponding comparator for the priorities in this queue.

Complexity:

O(log(size()))

Parameters:

v - a node in the priority queue.

priority - the new priority of the node.

increasePriority

public void increasePriority(Node v,
                             double priority)

Increases the priority value of the given node.

Preconditions:

contains(v)

c.compare(p,getPriority(v)) > 0, where c is the corresponding comparator for the priorities in this queue.

Complexity:

O(log(size()))

changePriority

public void changePriority(Node v,
                           double p)

Changes the priority value of the given node.

Precondition:

contains(v)

Complexity:

O(log(size()))

removeMin

public Node removeMin()

Removes the node with smallest priority from this queue.

Specified by:

removeMin in interface DoubleNodePQ

Precondition:

!isEmpty()

Complexity:

O(log(size()))

Returns:

the removed node with smallest priority

getMin

public Node getMin()

Returns the node with smallest priority in this queue.

Specified by:

getMin in interface DoubleNodePQ

Precondition:

!isEmpty()

getMinPriority

public double getMinPriority()

Returns the minimum priority value in this queue.

contains

public boolean contains(Node v)

Returns whether or not the given node is contained in this queue.

Specified by:

contains in interface DoubleNodePQ

Complexity:

O(1)

isEmpty

public boolean isEmpty()

Returns whether or not this queue is empty

Specified by:

isEmpty in interface DoubleNodePQ

Complexity:

O(1)

size

public int size()

Returns the number of nodes currently in this queue

Complexity:

O(1)

getPriority

public double getPriority(Node v)

Returns the current priority of the given node.

Specified by:

getPriority in interface DoubleNodePQ

Precondition:

contains(v)

remove

public void remove(Node v)

Removes the given node from this queue.

Precondition:

contains(v)

Complexity:

O(log(size()))

clear

public void clear()

Makes this queue the empty queue. in this queue.

Specified by:

clear in interface DoubleNodePQ

Complexity:

O(graph.N())

dispose

public void dispose()

Does nothing.

Specified by:

dispose in interface DoubleNodePQ