import * as utils from '../utils';
/*******************************************************************************
 * A D-ary implements the Priority Queue ADT, just like the binary heap.
 * What's different is that it has d children.
 *
 * D-ary heaps are better for decreaseKey operations because decreaseKey()
 * means we must swim the node up (min heap). Since d > 2, log_d(n) < log_2(n),
 * meaning we swim up fewer levels.
 *
 * This is preferred for algorithms with heavy decreaseKey() calls like
 * Djikstra's shortest path and Prim's minimum spanning tree.
 *
 *
 * add(element) - O(log_dn) no comparisons needed for swimming up
 * poll() - O(dlog_dn) (d child comparisons when sinking to find min child)
 * decreaseKey() - O(log_dn) bc we swim up
 * peek() - O(1)
 *
 * More info can be found here: https://en.wikipedia.org/wiki/D-ary_heap
 ******************************************************************************/
declare class MinDHeap<T> {
    private heap;
    private d;
    private compare;
    constructor(degree: number, compareFunction?: utils.CompareFunction<T>);
    /*****************************************************************************
                                    INSPECTION
    *****************************************************************************/
    /**
     * 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 element to the heap, while maintaing the heap invariant - O(log_d(n))
     * @param {T} element
     * @returns {void}
     */
    add(element: T): void;
    /*****************************************************************************
                                    ACCESSING
    *****************************************************************************/
    /**
     * Peeks at the top most element in the heap - O(1)
     * @returns {T}
     */
    peek(): T | null;
    /*****************************************************************************
                                    SEARCHING
    *****************************************************************************/
    /**
     * Returns true if element is in heap, false otherwise - O(n)
     * @param {T} element
     * @returns {boolean}
     */
    contains(element: T): boolean;
    /*****************************************************************************
                                    DELETION
    *****************************************************************************/
    /**
     * Removes and returns top most element of heap - O(log_d(n))
     * @returns {T}
     */
    poll(): T | null;
    /**
     * Removes element if it exists. Returns true if success, false otherwise - O(n)
     * @param {T} element
     * @returns {boolean}
     */
    remove(element: T): boolean;
    /**
     * Clears the heap - O(1)
     * @returns {void}
     */
    clear(): void;
    /*****************************************************************************
                                    HELPERS
    *****************************************************************************/
    private getChildrenIndices;
    private getParentIndex;
    /**
     * Returns true if a is less than b, false otherwise
     * @param {number} a
     * @param {number} b
     */
    private less;
    /**
     * 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;
    /**
     * Removes element at provided index by swapping it with last element, and
     * heapifying the swapped element by sinking/swimming it - O(dlog(n)).
     *
     * O(dlog(n)) because in worst case we have to sink element throughout entire
     * tree
     * @param {number} indexToRemove
     * @returns {T}
     * @throws {OUT_OF_BOUNDS_ERROR, EMPTY_ERROR}
     */
    private removeAt;
}
export default MinDHeap;
//# sourceMappingURL=min-d-heap.d.ts.map