Packagecom.yworks.yfiles.util.pq
Classpublic class BHeapNodePQ
InheritanceBHeapNodePQ Inheritance YObject Inheritance 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 com.yworks.yfiles.util.pq.BHeapDoubleNodePQ is slightly more efficient than using this generic NodePQ.

See also

com.yworks.yfiles.util.pq.BHeapDoubleNodePQ

Public Properties
 PropertyDefined By
  empty : Boolean
[read-only] Returns whether or not this queue is empty Complexity O(1)
BHeapNodePQ
  min : Node
[read-only] Returns he node with smallest priority in this queue.
BHeapNodePQ
  minPriority : Object
[read-only] Returns the minimum priority value in this queue.
BHeapNodePQ
Public Methods
 MethodDefined By
  
BHeapNodePQ(graph:Graph, c:Comparator, init:Boolean = true)
Creates an empty NodePQ for nodes contained in the given graph.
BHeapNodePQ
  
add(v:Node, priority:Object):void
Adds the given node with with given priority to this queue.
BHeapNodePQ
  
changePriority(v:Node, priority:Object):void
Changes the priority value of the given node.
BHeapNodePQ
  
clear():void
Makes this queue the empty queue.
BHeapNodePQ
  
contains(v:Node):Boolean
Returns whether or not the given node is contained in this queue.
BHeapNodePQ
  
decreasePriority(v:Node, priority:Object):void
Decreases the priority value of the given node.
BHeapNodePQ
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
BHeapNodePQ
  
getPriority(v:Node):Object
Returns the current priority of the given node.
BHeapNodePQ
 Inherited
hashCode():int
YObject
  
increasePriority(v:Node, priority:Object):void
BHeapNodePQ
  
newBHeapNodePQ1(graph:Graph, c:Comparator):BHeapNodePQ
[static] Creates an empty NodePQ for nodes contained in the given graph.
BHeapNodePQ
  
newBHeapNodePQ2(graph:Graph, c:Comparator, dynamicMap:NodeMap):BHeapNodePQ
[static] Creates an empty NodePQ for nodes contained in the given graph.
BHeapNodePQ
  
remove(v:Node):void
Removes the given node from this queue.
BHeapNodePQ
  
removeMin():Node
Removes the node with smallest priority from this queue Precondition !isEmpty() Complexity O(log(size()))
BHeapNodePQ
  
size():int
Returns the number of nodes currently in this queue Complexity O(1)
BHeapNodePQ
Protected Methods
 MethodDefined By
  
initBHeapNodePQ1(graph:Graph, c:Comparator):void
Initializes this object.
BHeapNodePQ
  
initBHeapNodePQ2(graph:Graph, c:Comparator, dynamicMap:NodeMap):void
Initializes this object.
BHeapNodePQ
Property Detail
emptyproperty
empty:Boolean  [read-only]

Returns whether or not this queue is empty

Complexity O(1)


Implementation
    public function get empty():Boolean
minproperty 
min:Node  [read-only]

Returns he node with smallest priority in this queue.

Precondition !isEmpty()


Implementation
    public function get min():Node
minPriorityproperty 
minPriority:Object  [read-only]

Returns the minimum priority value in this queue.


Implementation
    public function get minPriority():Object
Constructor Detail
BHeapNodePQ()Constructor
public function BHeapNodePQ(graph:Graph, c:Comparator, init:Boolean = true)

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.

Parameters
graph:Graph
 
c:Comparator
 
init:Boolean (default = true) — An internally used switch to help handle proper instance initialization in inheritance chains where classes can have multiple constructor-like factory methods. This parameter can safely be ignored/omitted when calling the constructor.
Method Detail
add()method
public function add(v:Node, priority:Object):void

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

Precondition !contains(v)

Complexity O(log(size()))

Parameters

v:Node
 
priority:Object

changePriority()method 
public function changePriority(v:Node, priority:Object):void

Changes the priority value of the given node.

Precondition contains(v)

Complexity O(log(size()))

Parameters

v:Node
 
priority:Object

clear()method 
public function clear():void

Makes this queue the empty queue. in this queue.

Complexity O(graph.N())

contains()method 
public function contains(v:Node):Boolean

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

Complexity O(1)

Parameters

v:Node

Returns
Boolean
decreasePriority()method 
public function decreasePriority(v:Node, priority:Object):void

Decreases the priority value of the given node.

Precondition contains(v)

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

Complexity O(log(size()))

Parameters

v:Node
 
priority:Object

getClass()method 
override public function getClass():Class

Returns
Class
getPriority()method 
public function getPriority(v:Node):Object

Returns the current priority of the given node.

Precondition contains(v)

Parameters

v:Node

Returns
Object
increasePriority()method 
public function increasePriority(v:Node, priority:Object):void

Parameters

v:Node
 
priority:Object

initBHeapNodePQ1()method 
protected final function initBHeapNodePQ1(graph:Graph, c:Comparator):void

Initializes this object. See the documentation of the corresponding factory method newBHeapNodePQ1() for details.

Parameters

graph:Graph
 
c:Comparator

See also

newBHeapNodePQ1()
initBHeapNodePQ2()method 
protected final function initBHeapNodePQ2(graph:Graph, c:Comparator, dynamicMap:NodeMap):void

Initializes this object. See the documentation of the corresponding factory method newBHeapNodePQ2() for details.

Parameters

graph:Graph
 
c:Comparator
 
dynamicMap:NodeMap

See also

newBHeapNodePQ2()
newBHeapNodePQ1()method 
public static function newBHeapNodePQ1(graph:Graph, c:Comparator):BHeapNodePQ

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.

Parameters

graph:Graph
 
c:Comparator

Returns
BHeapNodePQ
newBHeapNodePQ2()method 
public static function newBHeapNodePQ2(graph:Graph, c:Comparator, dynamicMap:NodeMap):BHeapNodePQ

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.

Parameters

graph:Graph
 
c:Comparator
 
dynamicMap:NodeMap

Returns
BHeapNodePQ
remove()method 
public function remove(v:Node):void

Removes the given node from this queue.

Precondition contains(v)

Complexity O(log(size()))

Parameters

v:Node

removeMin()method 
public function removeMin():Node

Removes the node with smallest priority from this queue

Precondition !isEmpty()

Complexity O(log(size()))

Returns
Node — the removed node with smallest priority
size()method 
public function size():int

Returns the number of nodes currently in this queue

Complexity O(1)

Returns
int




Wed Oct 7 2015, 04:43 PM +02:00