/**
 * From http://eloquentjavascript.net/appendix2.html,
 * licensed under CCv3.0: http://creativecommons.org/licenses/by/3.0/
 */ function nodeEqual ( source , target ) { if ( typeof source === 'object' || typeof target === 'object' ) { return JSON . stringify ( source ) === JSON . stringify ( target ) ; } else { return source === target ; } } export class BinaryHeap { content ; scoreFunction ; constructor ( scoreFunction ) { this . content = [ ] ; this . scoreFunction = scoreFunction ; } clone ( ) { let heap = new BinaryHeap ( this . scoreFunction ) ; heap . content = JSON . parse ( JSON . stringify ( this . content ) ) ; return heap ; } push ( element ) { this . content . push ( element ) ; this . bubbleUp ( this . content . length - 1 ) ; } peek ( ) { return this . content [ 0 ] ; } pop ( ) { let result = this . content [ 0 ] ; let end = this . content . pop ( ) ; if ( this . content . length > 0 ) { this . content [ 0 ] = end ; this . sinkDown ( 0 ) ; } return result ; } remove ( node ) { let len = this . content . length ; for ( let i = 0 ; i < len ; i ++ ) { if ( nodeEqual ( this . content [ i ] , node ) ) { let end = this . content . pop ( ) ; if ( i !== len - 1 ) { this . content [ i ] = end ; if ( this . scoreFunction ( end ) < this . scoreFunction ( node ) ) { this . bubbleUp ( i ) ; } else { this . sinkDown ( i ) ; } } return true ; } } throw new Error ( 'Node not found.' ) ; } size ( ) { return this . content . length ; } bubbleUp ( n ) { let element = this . content [ n ] ; while ( n > 0 ) { let parentN = Math . floor ( ( n + 1 ) / 2 ) - 1 , parent = this . content [ parentN ] ; if ( this . scoreFunction ( element ) < this . scoreFunction ( parent ) ) { this . content [ parentN ] = element ; this . content [ n ] = parent ; n = parentN ; } else { break ; } } } sinkDown ( n ) { let length = this . content . length , element = this . content [ n ] , elemScore = this . scoreFunction ( element ) ; while ( true ) { let child2N = ( n + 1 ) * 2 , child1N = child2N - 1 ; let swap = null ; let child1Score ; if ( child1N < length ) { let child1 = this . content [ child1N ] ; child1Score = this . scoreFunction ( child1 ) ; if ( child1Score < elemScore ) { swap = child1N ; } } if ( child2N < length ) { let child2 = this . content [ child2N ] , child2Score = this . scoreFunction ( child2 ) ; if ( child2Score < ( swap == null ? elemScore : child1Score ) ) { swap = child2N ; } } if ( swap != null ) { this . content [ n ] = this . content [ swap ] ; this . content [ swap ] = element ; n = swap ; } else { break ; } } } }