/**
 * Interface for a comparere
 */ export interface IComparer < T > { /**
     * The minimum value of type T
     */ min : T ; returns compare ( a , b ) : number ; } /**
 * A comparer for numbers
 */ export const NumberComparer = { returns compare : ( a , b ) => a - b , /**
     * The minimum value of a javascript number, which is Number.MIN_VALUE
     */ min : Number . MIN_VALUE , } ; /**
 * Interface to a node in Heap
 */ export interface IHeapNode < T > { value : T ; position : number ; } /**
 * Ordered Heap data structure implementation
 */ export class Heap < T > { private L : IHeapNode < T > [ ] ; param comp constructor ( public comp ) { this . L = [ { value : comp . min , position : 0 } ] ; } returns public peek ( ) { return this . L [ 1 ] ; } returns public get ( ) { this . swap ( 1 , this . count ( ) ) ; const x = this . L . pop ( ) ; this . fixdown ( 1 ) ; return x ! . value ; } param x returns public add ( x ) { const node = { value : x , position : this . L . length } ; this . L . push ( node ) ; this . fixup ( this . count ( ) ) ; return node ; } /**
     * Allows for heap to be updated after a node's value changes
     */ public update ( node ) { const k = node . position ; if ( this . isGreaterThanParent ( k ) ) { this . fixup ( k ) ; } else { this . fixdown ( k ) ; } } param node public remove ( node ) { const position = node . position ; this . swap ( node . position , this . L . length - 1 ) ; this . L . splice ( this . L . length - 1 ) ; if ( position !== this . L . length ) { this . update ( this . L [ position ] ) ; } } returns public count ( ) { return this . L . length - 1 ; } private fixup ( pos ) { let k = pos ; while ( this . isGreaterThanParent ( k ) ) { const parent = k >> 1 ; this . swap ( k , parent ) ; k = parent ; } } private isGreaterThanParent ( k ) { return k > 1 && ( this . comp . compare ( this . L [ k >> 1 ] . value , this . L [ k ] . value ) > 0 ) ; } private fixdown ( pos ) { let k = pos ; while ( ( k << 1 ) <= this . count ( ) ) { let j = k << 1 ; if ( ( j < this . count ( ) ) && ( this . comp . compare ( this . L [ j ] . value , this . L [ j + 1 ] . value ) > 0 ) ) { j ++ ; } if ( this . comp . compare ( this . L [ k ] . value , this . L [ j ] . value ) <= 0 ) { break ; } this . swap ( k , j ) ; k = j ; } } private swap ( k , j ) { const tmp = this . L [ k ] ; this . L [ k ] = this . L [ j ] ; this . L [ k ] . position = k ; this . L [ j ] = tmp ; this . L [ j ] . position = j ; } }