import { CompareFunction } from "@tiny-calc/types" ; export class Heap < T > { public constructor ( private readonly compareFn , private readonly items = [ ] ) { for ( let i = ( this . length >>> 1 ) - 1 ; i >= 0 ; i -- ) { this . down ( i ) ; } } /** Returns the number of items in the heap. */ public get length ( ) : number { return this . items . length ; } /** Returns the item currently at the top of the heap  */ public peek ( ) { return this . items [ 0 ] ; } /** Removes the item current at the top of the heap and returns it. */ public pop ( ) { const top = this . peek ( ) ; const bottom = this . items . pop ( ) ; if ( this . length > 0 ) { this . items [ 0 ] = bottom ! ; this . down ( 0 ) ; } return top ; } /** Inserts the item in to the heap. */ public push ( item ) { this . items . push ( item ) ; this . up ( this . items . length - 1 ) ; } /** Removes all items from the heap in O(1) time. */ public clear ( ) { this . items . length = 0 ; } /**
     * Sift the child upwards by swapping with its current parent until the parent is
     * <= the child.
     */ private up ( child ) { while ( child > 0 ) { const parent = ( child - 1 ) >>> 1 ; if ( this . compareFn ( this . items [ child ] , this . items [ parent ] ) >= 0 ) { break ; } const tmp = this . items [ parent ] ; this . items [ parent ] = this . items [ child ] ; this . items [ child ] = tmp ; child = parent ; } } /**
     * Sift the parent downwards by swapping with its minimum child until the parent
     * is <= its children.
     */ private down ( parent ) { while ( parent < ( this . length >>> 1 ) ) { let child = ( parent << 1 ) + 1 ; if ( ( ( child + 1 ) < this . length ) && ( this . compareFn ( this . items [ child ] , this . items [ child + 1 ] ) > 0 ) ) { child ++ ; } if ( this . compareFn ( this . items [ parent ] , this . items [ child ] ) <= 0 ) { break ; } const tmp = this . items [ parent ] ; this . items [ parent ] = this . items [ child ] ; this . items [ child ] = tmp ; parent = child ; } } }