y.util.pq
Class BHeapNodePQ

java.lang.Object
  y.util.pq.BHeapNodePQ

All Implemented Interfaces:

NodePQ

public class BHeapNodePQ
extends java.lang.Object
implements NodePQ

This class represents a priority queue for nodes where the priority values are of type Object The implementation is based on binary heaps.

In case the priority values are of type double then using BHeapDoubleNodePQ is slightly more efficient than using this generic NodePQ.

Constructor Summary

BHeapNodePQ(Graph graph, java.util.Comparator c)
Creates an empty NodePQ for nodes contained in the given graph.

BHeapNodePQ(Graph graph, java.util.Comparator c, NodeMap dynamicMap)
Creates an empty NodePQ for nodes contained in the given graph.

Method Summary

void	add(Node v, java.lang.Object priority) Adds the given node with with given priority to this queue.
void	changePriority(Node v, java.lang.Object priority) 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, java.lang.Object priority) Decreases the priority value of the given node.
Node	getMin() Returns the node with smallest priority in this queue.
java.lang.Object	getMinPriority() Returns the minimum priority value in this queue.
java.lang.Object	getPriority(Node v) Returns the current priority of the given node.
void	increasePriority(Node v, java.lang.Object 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

BHeapNodePQ

public BHeapNodePQ(Graph graph,
                   java.util.Comparator c)

Creates an empty NodePQ for nodes contained in the given graph. The given comparator must be able to compare all nodes residing in this queue by their priority. Neither the node set nor the indices of the nodes of the given graph may change while this queue is being used.

BHeapNodePQ

public BHeapNodePQ(Graph graph,
                   java.util.Comparator c,
                   NodeMap dynamicMap)

Creates an empty NodePQ for nodes contained in the given graph. The given comparator must be able to compare all nodes residing in this queue by their priority. By providing a NodeMap that can handle dynamic changes of its definition range this queue will be enabled to function even when the node set of the given graph changes.

Method Detail

add

public void add(Node v,
                java.lang.Object priority)

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

Specified by:

add in interface NodePQ

Precondition:

!contains(v)

Complexity:

O(log(size()))

decreasePriority

public void decreasePriority(Node v,
                             java.lang.Object priority)

Decreases the priority value of the given node.

Specified by:

decreasePriority in interface NodePQ

Preconditions:

contains(v)

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

Complexity:

O(log(size()))

increasePriority

public void increasePriority(Node v,
                             java.lang.Object priority)

Increases the priority value of the given node.

Preconditions:

contains(v)

c.compare(priority,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,
                           java.lang.Object priority)

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 NodePQ

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 NodePQ

Precondition:

!isEmpty()

getMinPriority

public java.lang.Object getMinPriority()

Returns the minimum priority value in this queue.

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 NodePQ

Complexity:

O(graph.N())

contains

public boolean contains(Node v)

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

Specified by:

contains in interface NodePQ

Complexity:

O(1)

isEmpty

public boolean isEmpty()

Returns whether or not this queue is empty

Specified by:

isEmpty in interface NodePQ

Complexity:

O(1)

size

public int size()

Returns the number of nodes currently in this queue

Specified by:

size in interface NodePQ

Complexity:

O(1)

getPriority

public java.lang.Object getPriority(Node v)

Returns the current priority of the given node.

Specified by:

getPriority in interface NodePQ

Precondition:

contains(v)