/**
 * A compare function to determine if a is 'better' (deserves a higher position) than b
 */ export type Comparator < E > = ( a : E , b : E ) => boolean ; /**
 * Minimalist Implementation of the heap data structure as an array
 */ class Heap < E > { private elements : E [ ] = [ ] ; readonly compare : Comparator < E > ; constructor ( compare ) { this . compare = compare ; } /**
     * Returns the size of the heap
     */ getSize ( ) { return this . elements . length ; } /**
     * Checks if heap is empty
     */ isEmpty ( ) { return this . elements . length === 0 ; } param e push ( e ) { this . elements . push ( e ) ; this . siftUp ( this . elements . length - 1 ) ; } /**
     * Returns the top of the heap without removing it
     * Fails if heap is empty
     */ peek ( ) { return this . elements [ 0 ] ; } /**
     * Returns the top of the heap and removes it
     * Fails if heap is empty
     */ pop ( ) { const val = this . peek ( ) ; this . move ( this . elements . length - 1 , 0 ) ; this . elements . pop ( ) ; this . siftDown ( 0 ) ; return val ; } /**
     * Clear the heap
     */ clear ( ) { this . elements = [ ] ; } param pos private siftUp ( pos ) { let parent = ( ( pos - 1 ) / 2 ) >> 0 ; while ( parent >= 0 ) { if ( this . compare ( this . elements [ pos ] , this . elements [ parent ] ) ) { this . swap ( pos , parent ) ; pos = parent ; parent = ( ( pos - 1 ) / 2 ) >> 0 ; } else { parent = - 1 ; } } } param pos private siftDown ( pos ) { const left = 2 * pos + 1 ; const right = 2 * pos + 2 ; if ( left >= this . elements . length ) { return ; } const child = ( right >= this . elements . length || this . compare ( this . elements [ left ] , this . elements [ right ] ) ) ? left : right ; if ( this . compare ( this . elements [ child ] , this . elements [ pos ] ) ) { this . swap ( child , pos ) ; this . siftDown ( child ) ; } } param from param to private move ( from , to ) { this . elements [ to ] = this . elements [ from ] ; } param a param b private swap ( a , b ) { let val = this . elements [ a ] ; this . elements [ a ] = this . elements [ b ] ; this . elements [ b ] = val ; } } export default Heap ;