File Explorer

1/*2 * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.3 * SPDX-License-Identifier: Apache-2.0.4 */5 6import {CrtError} from "./error";7 8/**9 * A generic array-based min-heap implementation for priority queue usage.  Used to track operation timeouts.10 */11export class MinHeap<T> {12 13    private heap : Array<T | undefined> = [undefined];14    private currentSize: number = 0;15 16    constructor(private lessThanOperator: (lhs: T, rhs: T) => boolean) {17    }18 19    /**20     * Push a value into the min-heap21     *22     * @param value value to add23     */24    push(value: T) {25        this.currentSize++;26        this.heap[this.currentSize] = value;27        this.heapifyUp(this.currentSize);28    }29 30    /**31     * Gets the minimum value of the heap.  Returns undefined if the heap is empty.32     */33    peek() : T | undefined {34        if (this.currentSize == 0) {35            return undefined;36        }37 38        // guaranteed to be a T39        return this.heap[1];40    }41 42    /**43     * Pops the minimum value from the heap.  Throws an exception if the heap is empty.44     */45    pop() : T {46        if (this.empty()) {47            throw new CrtError("Heap is empty");48        }49 50        let returnValue = this.heap[1];51        let lastElement = this.heap[this.currentSize];52        this.heap[this.currentSize--] = undefined; // erase the reference; unclear if this is overkill rather than simply removing from an array (or an indexed map for that matter)53        this.heap[1] = lastElement;54        this.heapifyDown(1);55 56        // @ts-ignore - guaranteed to be a T57        return returnValue;58    }59 60    /**61     * Checks if the min-heap is empty or not62     */63    empty() : boolean {64        return this.currentSize == 0;65    }66 67    /**68     * Removes all values from the min-heap69     */70    clear() {71        this.heap = [undefined];72        this.currentSize = 0;73    }74 75    private swapElements(index1: number, index2: number) {76        let temp = this.heap[index1];77        this.heap[index1] = this.heap[index2];78        this.heap[index2] = temp;79    }80 81    private heapifyDown(startIndex: number) {82        let currentIndex : number = startIndex;83 84        while (true) {85            let leftIndex = currentIndex << 1;86            let rightIndex = leftIndex + 1;87            let swapIndex = undefined;88 89            // @ts-ignore - heap elements guaranteed to be a T90            if (leftIndex <= this.currentSize && this.lessThanOperator(this.heap[leftIndex], this.heap[currentIndex])) {91                swapIndex = leftIndex;92            }93 94            // @ts-ignore - heap elements guaranteed to be a T95            if (rightIndex <= this.currentSize && this.lessThanOperator(this.heap[rightIndex], this.heap[currentIndex])) {96                // @ts-ignore - heap elements guaranteed to be a T97                if (!swapIndex || this.lessThanOperator(this.heap[rightIndex], this.heap[leftIndex])) {98                    // if current is greater than both left and right children, we must swap with the smallest child99                    // since it will become the parent of both current and the other child100                    swapIndex = rightIndex;101                }102            }103 104            if (!swapIndex) {105                break;106            }107 108            this.swapElements(currentIndex, swapIndex);109            currentIndex = swapIndex;110        }111    }112 113    private heapifyUp(index: number) {114        let parentIndex = index >> 1;115        // @ts-ignore - heap element guaranteed to be a T116        while (parentIndex > 0 && this.lessThanOperator(this.heap[index], this.heap[parentIndex])) {117            this.swapElements(index, parentIndex);118            index = parentIndex;119            parentIndex = parentIndex >> 1;120        }121    }122}