import * as utils from '../utils';
/*******************************************************************************
 * An indexed version of the min D-heap. For more information on D-heaps, see
 * ./min-d-heap.ts
 *
 * This version of a heap allows us to add key value pairs. This gives us
 * logarithmic removals and updates, instead of linear.
 *
 * We could add do this in a hacky way by adding a mapping from values to indices.
 * So if we wanted to update or remove a specific value we know the index in the heap
 * in O(1) time.
 *
 * But then using non-primitive complex objects become a hassle. We have to tell
 * the heap class how to access the value. A better solution is to base it off
 * unique keys associated with all the nodes.
 *
 * enqueue(val) - O(log_d(n))
 * dequeue() - O(log_d(n))
 * peek() - O(1)
 * remove(val) - O(log_d(n))! improved from O(n)
 * update(key, val) - O(log_d(n))! improved from O(n)
 * decreaseKey(key, val) - O(log_d(n))! improved from O(n)
 * increaseKey(key, val) - O(log_d(n))! improved from O(n)
 *
 * More info can be found here: https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html
 ******************************************************************************/
declare class MinIndexedDHeap<T> {
    private d;
    private sz;
    private values;
    heap: number[];
    pm: number[];
    private compare;
    constructor(degree: number, compareFunction?: utils.CompareFunction<T>);
    /*****************************************************************************
                                    NICETIES
    *****************************************************************************/
    /**
     * Returns the size of the heap - O(1)
     * @returns {number}
     */
    size(): number;
    /**
     * Returns true if the heap is empty, false otherwise - O(1)
     * @returns {boolean}
     */
    isEmpty(): boolean;
    /*****************************************************************************
                                    INSERTION
    *****************************************************************************/
    /**
     * Adds an value with index to the heap, while maintaing heap invariant - O(log_d(n))
     * @param {number} key - index of node
     * @param {T} value - value of node
     * @returns {void}
     */
    add(key: number, value: T): boolean;
    /*****************************************************************************
                                    ACCESSING
    *****************************************************************************/
    /**
     * Peeks at the top most element in the heap - O(1)
     * @returns {T}
     */
    peek(): T | null;
    valueOf(key: number): T | null;
    /*****************************************************************************
                                    UPDATING
    *****************************************************************************/
    updateKey(key: number, value: T): boolean;
    decreaseKey(key: number, newValue: T): boolean;
    increaseKey(key: number, newValue: T): boolean;
    /*****************************************************************************
                                    SEARCHING
    *****************************************************************************/
    /**
     * Returns true if key is in heap, false otherwise - O(1)
     * @param {number} key
     * @returns {boolean}
     */
    contains(key: number): boolean;
    /*****************************************************************************
                                    DELETION
    *****************************************************************************/
    /**
     * Removes and returns top most element of heap - O(log_d(n))
     * @returns {T}
     */
    poll(): T | null;
    deleteKey(key: number): T | null;
    /**
     * Clears the heap - O(1)
     * @returns {void}
     */
    clear(): void;
    /*****************************************************************************
                                    HELPERS
    *****************************************************************************/
    private getChildrenPositions;
    private getParentPosition;
    /**
     * Returns true if value of value at positionA is less than value at positionB
     * @param {number} positionA
     * @param {number} positionB
     */
    private lessForPositions;
    private lessForValues;
    /**
     * Sinks element with index k until heap invariant is satisfied - O(dlog(n))
     * O(dlog(n)) because in the worst case we sink the element down the entire
     * height of the tree. At each level, we have to do d comparisons to find
     * smallest child to swim down.
     * @param {number} k
     * @returns {void}
     */
    private sink;
    /**
     * Swims an element with index k until heap invariant is satisfied - O(log_d(n))
     * O(logd(n)) because in the worst case we swim the element up the entire tree
     * @param {number} k
     * @returns {void}
     */
    private swim;
    private swap;
}
export default MinIndexedDHeap;
//# sourceMappingURL=min-indexed-d-heap.d.ts.map