    package flare.util.heap
    {
        /**
         * A Fibonacci heap data structure for maintaining a sorted priority queue.
         * For more about this particular implementation see
         * <a target="_top" href="http://en.wikipedia.org/wiki/Fibonacci_heap">
         * Wikipedia's Fibonacci Heap article</a>.
         */
        public class FibonacciHeap
        {
            private var _min:HeapNode;
            private var _size:int;

            /** True if the heap is empty, false otherwise. */
            public function get empty():Boolean
            {
                return _min == null;
            }

            /** The number of nodes contained in this heap. */
            public function get size():int
            {
                return _size;
            }

            /**
             * Clears the heap, removing all nodes.
             */
            public function clear():void
            {
                _min = null;
                _size = 0;
            }

            /**
             * Decrease the key value for a heap node, changing its key and
             * potentially re-configuring the heap structure
             * @param x the heap node
             * @param k the new key value for the node. If this value is greater
             *  than the node's current key value an error will be thrown.
             */
            public function decreaseKey(x:HeapNode, k:Number):void
            {
                if (k > x.key)
                    throw new Error("Only lower key values allowed");

                x.key = k;
                var y:HeapNode = x.parent;

                if ((y != null) && (x.key < y.key)) {
                    cut(x, y);
                    cascadingCut(y);
                }

                if (x.key < _min.key) {
                    _min = x;
                }
            }

            /**
             * Removes a node from the heap.
             * @param x the heap node to remove
             */
            public function remove(x:HeapNode):void
            {
                decreaseKey(x, Number.NEGATIVE_INFINITY);
                removeMin();
            }

            /**
             * Inserts a new node into the heap.
             * @param data the data to associate with the heap node
             * @param key the key value used to sort the heap node
             * @return the newly added heap node
             */
            public function insert(data:Object,
                key:Number=Number.POSITIVE_INFINITY):HeapNode
            {
                var n:HeapNode = new HeapNode(data, key);
                n.inHeap = true;

                if (_min != null) {
                    n.left = _min;
                    n.right = _min.right;
                    _min.right = n;
                    n.right.left = n;

                    if (key < _min.key)
                        _min = n;
                } else {
                    _min = n;
                }
                _size++;
                return n;
            }

            /**
             * Returns the heap node with the minimum key value.
             * @return the heap node with the minimum key value
             */
            public function min():HeapNode
            {
                return _min;
            }

            /**
             * Removes and returns the heap node with the minimum key value.
             * @return the heap node with the minimum key value
             */
            public function removeMin():HeapNode
            {
                var z:HeapNode = _min;
                if (z == null) return z;

                var kids:int = z.degree;
                var x:HeapNode = z.child;
                var r:HeapNode;

                // for each child of z do...
                while (kids > 0) {
                    r = x.right;

                    // remove x from child list
                    x.left.right = x.right;
                    x.right.left = x.left;

                    // add x to root list of heap
                    x.left = _min;
                    x.right = _min.right;
                    _min.right = x;
                    x.right.left = x;

                    // set parent[x] to null
                    x.parent = null;
                    x = r;
                    kids--;
                }

                // remove z from root list of heap
                z.left.right = z.right;
                z.right.left = z.left;

                if (z == z.right) {
                    _min = null;
                } else {
                    _min = z.right;
                    consolidate();
                }

                // decrement size of heap and return
                _size--;
                  z.inHeap = false;
                return z;
            }

            /**
             * Constructs the union of two fibonacci heaps.
             * @param h1 the first heap
             * @param h2 the second heap
             * @return the union of the two heaps
             */
            public static function union(h1:FibonacciHeap, h2:FibonacciHeap):FibonacciHeap
            {
                var h:FibonacciHeap = new FibonacciHeap();

                if (h1 != null && h2 != null) {
                    h._min = h1._min;

                    if (h._min != null) {
                        if (h2._min != null) {
                            h._min.right.left = h2._min.left;
                            h2._min.left.right = h._min.right;
                            h._min.right = h2._min;
                            h2._min.left = h._min;
                            if (h2._min.key < h1._min.key)
                                h._min = h2._min;
                        }
                    } else {
                        h._min = h2._min;
                    }

                    h._size = h1._size + h2._size;
                }

                return h;
            }

            private function cascadingCut(y:HeapNode):void
            {
                var z:HeapNode = y.parent;
                if (z != null) {
                    if (!y.mark) {
                        y.mark = true;
                    } else {
                        cut(y, z);
                        cascadingCut(z);
                    }
                }
            }

            private function consolidate():void
            {
                var arraySize:int = _size + 1;
                var array:Array = new Array(arraySize);
                var i:uint;

                // Initialize degree array
                for (i=0; i<arraySize; i++)
                    array[i] = null;

                // Find the number of root nodes.
                var numRoots:int = 0, d:int;
                var x:HeapNode = _min, y:HeapNode;
                var next:HeapNode, temp:HeapNode;

                if (x != null) {
                    numRoots++;
                    x = x.right;

                    while (x != _min) {
                        numRoots++;
                        x = x.right;
                    }
                }

                // For each node in root list do...
                while (numRoots > 0) {
                    // Access this node's degree..
                    d = x.degree;
                    next = x.right;

                    // ..and see if there's another of the same degree.
                    while (array[d] != null) {
                        // There is, make one of the nodes a child of the other.
                        y = array[d];

                        // Do this based on the key value.
                        if (x.key > y.key) {
                            temp = y;
                            y = x;
                            x = temp;
                        }

                        // FiboHeapNode y disappears from root list.
                        link(y, x);

                        // We've handled this degree, go to next one.
                        array[d] = null;
                        d++;
                    }

                    // Save this node for later when we might encounter another
                    // of the same degree.
                    array[d] = x;

                    // Move forward through list.
                    x = next;
                    numRoots--;
                }

                // Set min to null (effectively losing the root list) and
                // reconstruct the root list from the array entries in array[].
                _min = null;

                for (i=0; i<arraySize; i++) {
                    if (array[i] != null) {
                        // We've got a live one, add it to root list.
                        if (_min != null) {
                            // First remove node from root list.
                            array[i].left.right = array[i].right;
                            array[i].right.left = array[i].left;

                            // Now add to root list, again.
                            array[i].left = _min;
                            array[i].right = _min.right;
                            _min.right = array[i];
                            array[i].right.left = array[i];

                            // Check if this is a new min.
                            if (array[i].key < _min.key) {
                                _min = array[i];
                            }
                        } else {
                            _min = array[i];
                        }
                    }
                }
            }

            private function cut(x:HeapNode, y:HeapNode):void
            {
                // remove x from childlist of y and decrement degree[y]
                x.left.right = x.right;
                x.right.left = x.left;
                y.degree--;

                // reset y.child if necessary
                if (y.child == x) {
                    y.child = x.right;
                }

                if (y.degree == 0) {
                    y.child = null;
                }

                // add x to root list of heap
                x.left = _min;
                x.right = _min.right;
                _min.right = x;
                x.right.left = x;

                // set parent[x] to nil
                x.parent = null;

                // set mark[x] to false
                x.mark = false;
            }

            private function link(y:HeapNode, x:HeapNode):void
            {
                // remove y from root list of heap
                y.left.right = y.right;
                y.right.left = y.left;

                // make y a child of x
                y.parent = x;

                if (x.child == null) {
                    x.child = y;
                    y.right = y;
                    y.left = y;
                } else {
                    y.left = x.child;
                    y.right = x.child.right;
                    x.child.right = y;
                    y.right.left = y;
                }

                // increase degree[x]
                x.degree++;

                // set mark[y] false
                y.mark = false;
            }

        } // end of class FibonacciHeap
    }