y.util.pq
Class BHeapIntNodePQ

java.lang.Object
  |
  +--y.util.pq.BHeapIntNodePQ
All Implemented Interfaces:
IntNodePQ

public class BHeapIntNodePQ
extends Object
implements IntNodePQ

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

The implementation is based on binary heaps.


Constructor Summary
BHeapIntNodePQ(Graph graph)
          Creates an empty NodePQ for nodes contained in the given graph.
 
Method Summary
 void add(Node v, int priority)
          Adds the given node with with given priority to this queue.
 void changePriority(Node v, int 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, int priority)
          Decreases the priority value of the given node.
 void dispose()
          Does nothing.
 Node getMin()
          Returns he node with smallest priority in this queue.
 int getMinPriority()
          Returns the minimum priority value in this queue.
 int getPriority(Node v)
          Returns the current priority of the given node.
 void increasePriority(Node v, int 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

BHeapIntNodePQ

public BHeapIntNodePQ(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,
                int priority)
Adds the given node with with given priority to this queue.

Specified by:
add in interface IntNodePQ
Precondition:
!contains(v)
Complexity:
O(log(size()))

decreasePriority

public void decreasePriority(Node v,
                             int priority)
Decreases the priority value of the given node.

Specified by:
decreasePriority in interface IntNodePQ
Preconditions:
contains(v)
priority < getPriority(v)
Complexity:
O(log(size()))
Parameters:
v - a node in the priotity queue.
priority - the new priority value of the node.

increasePriority

public void increasePriority(Node v,
                             int priority)
Increases the priority value of the given node.

Preconditions:
contains(v)
priority > getPriority(v)
Complexity:
O(log(size()))

changePriority

public void changePriority(Node v,
                           int 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 IntNodePQ
Precondition:
!isEmpty()
Complexity:
O(log(size()))
Returns:
the removed node with smallest priority

getMin

public Node getMin()
Returns he node with smallest priority in this queue.

Specified by:
getMin in interface IntNodePQ
Precondition:
!isEmpty()

getMinPriority

public int 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 IntNodePQ
Complexity:
O(1)

isEmpty

public boolean isEmpty()
Returns whether or not this queue is empty

Specified by:
isEmpty in interface IntNodePQ
Complexity:
O(1)

size

public int size()
Returns the number of nodes currently in this queue

Complexity:
O(1)

getPriority

public int getPriority(Node v)
Returns the current priority of the given node.

Specified by:
getPriority in interface IntNodePQ
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 IntNodePQ
Complexity:
O(graph.N())

dispose

public void dispose()
Does nothing.

Specified by:
dispose in interface IntNodePQ

© Copyright 2000-2003,
yWorks GmbH.
All rights reserved.

2003