Packageflare.util.heap
Classpublic class FibonacciHeap

A Fibonacci heap data structure for maintaining a sorted priority queue. For more about this particular implementation see Wikipedia's Fibonacci Heap article.



Public Properties
 PropertyDefined by
  empty : Boolean
[read-only] True if the heap is empty, false otherwise.
FibonacciHeap
  size : int
[read-only] The number of nodes contained in this heap.
FibonacciHeap
Public Methods
 MethodDefined by
  
clear():void
Clears the heap, removing all nodes.
FibonacciHeap
  
decreaseKey(x:HeapNode, k:Number):void
Decrease the key value for a heap node, changing its key and potentially re-configuring the heap structure
FibonacciHeap
  
insert(data:Object, key:Number):HeapNode
Inserts a new node into the heap.
FibonacciHeap
  
Returns the heap node with the minimum key value.
FibonacciHeap
  
remove(x:HeapNode):void
Removes a node from the heap.
FibonacciHeap
  
Removes and returns the heap node with the minimum key value.
FibonacciHeap
  
[static] Constructs the union of two fibonacci heaps.
FibonacciHeap
Property detail
emptyproperty
empty:Boolean  [read-only]

True if the heap is empty, false otherwise.

Implementation
    public function get empty():Boolean
sizeproperty 
size:int  [read-only]

The number of nodes contained in this heap.

Implementation
    public function get size():int
Method detail
clear()method
public function clear():void

Clears the heap, removing all nodes.

decreaseKey()method 
public function decreaseKey(x:HeapNode, k:Number):void

Decrease the key value for a heap node, changing its key and potentially re-configuring the heap structure

Parameters
x:HeapNode — the heap node
 
k:Number — the new key value for the node. If this value is greater than the node's current key value an error will be thrown.
insert()method 
public function insert(data:Object, key:Number):HeapNode

Inserts a new node into the heap.

Parameters
data:Object — the data to associate with the heap node
 
key:Number — the key value used to sort the heap node

Returns
HeapNode — the newly added heap node
min()method 
public function min():HeapNode

Returns the heap node with the minimum key value.

Returns
HeapNode — the heap node with the minimum key value
remove()method 
public function remove(x:HeapNode):void

Removes a node from the heap.

Parameters
x:HeapNode — the heap node to remove
removeMin()method 
public function removeMin():HeapNode

Removes and returns the heap node with the minimum key value.

Returns
HeapNode — the heap node with the minimum key value
union()method 
public static function union(h1:FibonacciHeap, h2:FibonacciHeap):FibonacciHeap

Constructs the union of two fibonacci heaps.

Parameters
h1:FibonacciHeap — the first heap
 
h2:FibonacciHeap — the second heap

Returns
FibonacciHeap — the union of the two heaps