import FibonacciNode from './fibonacci-node';
import * as utils from '../../utils';
/*******************************************************************************
 * A fibonacci heap is a lazy binomial heap with lazy decreaseKey(). Some important
 * algorithms heavily rely on decreaseKey(). Dijkstra's shortest path, Prim's
 * minimum spanning tree. Fibonacci heaps give the theoretically optimal implementation
 * of Prim's and Dijkstra's algorithms.
 *
 * decreaseKey() is implemented as follows:
 *
 * If a node's value gets decreased such that it's value is less than it's parents,
 * (violating heap invariant), we don't swim it up. Instead, we cut the child off
 * from it's parent and make it a root in our list of roots.
 *
 * However, if we're allowed to cut off any number of nodes from a tree, than
 * our trees will degenerate into trees into shapes we don't want. A tree of
 * degree k will only have k + 1 nodes. Then, the number of nodes in the tree
 * is no longer exponential (2^k). This in turn makes decreaseKey() inefficient,
 * running in O(n) time.
 *
 * The problem is that a rank k tree thinks they're big. But the'yre losing all their
 * descendants. We need to convey to them that they're losing all their
 * children/descendants.
 *
 * We want the tree's to only become somewhat imbalanced, slowly propagating this
 * information to the root.
 *
 * Here's the solution:
 * ===================
 * Rule 1. Lose one child, you’re a loser.
 * Rule 2. Lose two, and you're dumped into the root list.
 *
 * If a node loses two children, we'll cut it from IT'S parent and move it to
 * our main root list.
 *
 * Then, a tree can only become "maximally damaged". The number of nodes in the
 * sequence of maximally damaged trees is the fibonacci sequence, hence the name
 * of the data structure.
 *
 * enqueue() - O(1)
 * extractMin() - O(logn) amortized
 * findMin() - O(1)
 * merge() - O(1)
 * decreaseKey() - O(1) ~~ down from O(logn) due to being lazy :)
 *
 * More info can be found here: https://en.wikipedia.org/wiki/Fibonacci_heap
 *
 * The implementation below is based off the Fibonacci Heap pseudocode from CLRS Chapter 20
 ******************************************************************************/
declare class MinFibonacciHeap<T> {
    head: FibonacciNode<T> | null;
    size: number;
    minRoot: FibonacciNode<T> | null;
    private smallestValue;
    private compare;
    constructor(smallestValue: T, compareFunction?: utils.CompareFunction<T>);
    /*****************************************************************************
                                    INSPECTION
    *****************************************************************************/
    /**
     * Returns true if the heap is empty, false otherwise - O(1)
     * @returns {boolean}
     */
    isEmpty(): boolean;
    /*****************************************************************************
                                    INSERTION/DELETION
    *****************************************************************************/
    /**
     * Enqueues element onto the heap - O(1)
     * @param {T} element
     * @returns {void}
     */
    enqueue(element: T): FibonacciNode<T>;
    /**
     * Dequeues the smallest element from the heap // O(logn)
     * @param {T} element
     * @returns {void}
     */
    dequeue(): FibonacciNode<T> | null;
    private removeSmallestRoot;
    private recalculateMin;
    /**
     * Deletes the given node - O(logn)
     * @param {FibonacciNode<T>} node
     * @returns {void}
     */
    deleteNode(node: FibonacciNode<T>): FibonacciNode<T> | null;
    /*****************************************************************************
                                    READING
    *****************************************************************************/
    /**
     * Returns the smallest node in the heap, null if the heap is empty O(1)
     * @returns {FibonacciNode<T> | null}
     */
    peek(): FibonacciNode<T> | null;
    /*****************************************************************************
                                    UPDATING
    *****************************************************************************/
    /**
     * Unions supplied heap with current heap - O(1). Current implementation
     * is destructive.
     * @param {FibonacciHeap<T>} otherHeap
     * @returns {FibonacciHeap<T>}
     */
    union(otherHeap: MinFibonacciHeap<T>): MinFibonacciHeap<T>;
    /**
     * Consolidates the current state of the heap such that only one tree exists
     * for degree k - O(t + logn)
     * @returns {MinFibonacciHeap<T>}
     */
    private consolidate;
    private linkTrees;
    private sortForest;
    /**
     * Decreases the value of the given node to the new value. If the new value is
     * smaller than it's parent, it lazily promotes the node to become a root of
     * the forest instead of swimming it up. Returns true if successful, and false
     * otherwise - O(1)
     * @param {FibonacciNode<T>} node
     * @param {T} newValue
     * @returns {boolean}
     */
    decreaseKey(node: FibonacciNode<T>, newValue: T): boolean;
    private cut;
    private cascadingCut;
}
export default MinFibonacciHeap;
//# sourceMappingURL=min-fibonacci-heap.d.ts.map