import BinomialNode from './binomial-node';
import * as utils from '../../utils';
/*******************************************************************************
 * A binomial heap is a forest of binomial trees.
 *
 * A binomial tree of degree 0 is a single node.
 * A binomial tree of degree k has a root node with k children. The degrees of those
 * children are k-1, k-2,..., 2, 1, 0.
 *
 * A binomial tree of degree k has 2^k nodes.
 *
 * A binomial heap is a forest of binomial trees that satisfy the heap invariant.
 * There can be only 0 or 1 binomial tree of degree k in the forest.
 *
 * The two key features of binomial heaps are:
 *
 * 1. The roots of the forest are <= log(n)
 * 2. Merging two heaps is binary addition
 *
 * This brings merge() from O(n + m) to O(logn + logm)!!!
 *
 * But because we now have a forest instead of one single tree, findMin() now
 * takes O(logn) to traverse the entire forest :( Check out the lazy binomial heap
 * to see how we can bring this back down to O(1)
 *
 * enqueue() - O(logn)
 * extractMin() - O(logn)
 * findMin() - O(1)
 * merge() - O(logn + logm) ~~~improved from O(n+m)!
 *
 * More info can be found here: https://en.wikipedia.org/wiki/Binomial_heap
 * The Implementation belowbased off Binomial Heap pseudocode from CLRS ed 2 (Chapter 19)
 ******************************************************************************/
declare class MinBinomialHeap<T> {
    head: BinomialNode<T> | null;
    size: number;
    minRoot: BinomialNode<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.
     * @param {T} element
     * @returns {void}
     */
    enqueue(element: T): BinomialNode<T>;
    /**
     * Dequeues the smallest element from the heap // O(logn)
     * @param {T} element
     * @returns {void}
     */
    dequeue(): BinomialNode<T> | null;
    /**
     * Deletes the given node - O(logn)
     * @param {BinomialNode<T>} node
     * @returns {void}
     */
    deleteNode(node: BinomialNode<T>): BinomialNode<T> | null;
    private removeSmallestRoot;
    private reverseListOfRoots;
    private recalculateMin;
    /*****************************************************************************
                                    READING
    *****************************************************************************/
    /**
     * Returns the smallest node in the heap, null if the heap is empty O(1)
     * @returns {BinomialNode<T> | null}
     */
    peek(): BinomialNode<T> | null;
    /*****************************************************************************
                                    UPDATING
    *****************************************************************************/
    /**
     * Unions supplied heap with current heap - O(logn + logm)
     * @param {MinBinomialHeap<T>} otherHeap
     * @returns {MinBinomialHeap<T>}
     */
    union(otherHeap: MinBinomialHeap<T>): MinBinomialHeap<T>;
    private linkTrees;
    private mergeForests;
    /**
     * Decreases the value of the given node to the new value. Returns true if
     * successful, and false otherwise - O(logn)
     * @param {BinomialNode<T>} node
     * @param {T} newValue
     * @returns {boolean}
     */
    decreaseKey(node: BinomialNode<T>, newValue: T): boolean;
}
export default MinBinomialHeap;
//# sourceMappingURL=min-binomial-heap.d.ts.map