export enum BinaryHeapMode { MIN , MAX } export interface PositionHeapEntry { score : number ; position : number ; } export interface IBinaryHeap { getMode ( ) : BinaryHeapMode ; getArray ( ) : Array < any > ; size ( ) : number ; getEvalPriorityFun ( ) : Function ; evalInputScore ( obj ) : number ; getEvalObjIDFun ( ) : Function ; evalInputObjID ( obj ) : any ; insert ( obj ) : void ; remove ( obj ) : any ; peek ( ) : any ; pop ( ) : any ; find ( obj ) : any ; getPositions ( ) : any ; } TODO class BinaryHeap implements IBinaryHeap { _nr_removes : number = 0 ; private _array = [ ] ; private _positions : { [ id ] : PositionHeapEntry ; } = { } ; param _mode param _evalObjID param _evalPriority constructor ( private _mode = BinaryHeapMode . MIN , private _evalPriority = ( obj ) : number => { if ( typeof obj !== "number" && typeof obj !== "string" ) { return NaN ; } if ( typeof obj === "number" ) { return obj | 0 ; } return parseInt ( obj ) ; } , private _evalObjID = ( obj ) : any => { return obj ; } ) { } getMode ( ) { return this . _mode ; } getArray ( ) { return this . _array ; } getPositions ( ) { return this . _positions ; } size ( ) { return this . _array . length ; } getEvalPriorityFun ( ) { return this . _evalPriority ; } evalInputScore ( obj ) { return this . _evalPriority ( obj ) ; } getEvalObjIDFun ( ) { return this . _evalObjID ; } evalInputObjID ( obj ) { return this . _evalObjID ( obj ) ; } peek ( ) { return this . _array [ 0 ] ; } pop ( ) { if ( this . size ( ) ) { return this . remove ( this . _array [ 0 ] ) ; } } find ( obj ) { let pos = this . getNodePosition ( obj ) ; return this . _array [ pos ] ; } param obj returns { number } insert ( obj ) { if ( isNaN ( this . _evalPriority ( obj ) ) ) { throw new Error ( "Cannot insert object without numeric priority." ) ; } todo this . _array . push ( obj ) ; this . setNodePosition ( obj , this . size ( ) - 1 ) ; this . trickleUp ( this . size ( ) - 1 ) ; } remove ( obj ) { this . _nr_removes ++ ; if ( isNaN ( this . _evalPriority ( obj ) ) ) { throw new Error ( "Object invalid." ) ; } let pos = this . getNodePosition ( obj ) , found = this . _array [ pos ] != null ? this . _array [ pos ] : null ; if ( found === null ) { return undefined ; } let last_array_obj = this . _array . pop ( ) ; this . removeNodePosition ( obj ) ; if ( this . size ( ) && found !== last_array_obj ) { this . _array [ pos ] = last_array_obj ; this . setNodePosition ( last_array_obj , pos ) ; this . trickleUp ( pos ) ; this . trickleDown ( pos ) ; } return found ; } private trickleDown ( i ) { let parent = this . _array [ i ] ; while ( true ) { let right_child_idx = ( i + 1 ) * 2 , left_child_idx = right_child_idx - 1 , right_child = this . _array [ right_child_idx ] , left_child = this . _array [ left_child_idx ] , swap = null ; if ( left_child_idx < this . size ( ) && ! this . orderCorrect ( parent , left_child ) ) { swap = left_child_idx ; } if ( right_child_idx < this . size ( ) && ! this . orderCorrect ( parent , right_child ) && ! this . orderCorrect ( left_child , right_child ) ) { swap = right_child_idx ; } if ( swap === null ) { break ; } this . _array [ i ] = this . _array [ swap ] ; this . _array [ swap ] = parent ; this . setNodePosition ( this . _array [ i ] , i ) ; this . setNodePosition ( this . _array [ swap ] , swap ) ; i = swap ; } } private trickleUp ( i ) { let child = this . _array [ i ] ; while ( i ) { let parent_idx = Math . floor ( ( i + 1 ) / 2 ) - 1 , parent = this . _array [ parent_idx ] ; if ( this . orderCorrect ( parent , child ) ) { break ; } else { this . _array [ parent_idx ] = child ; this . _array [ i ] = parent ; this . setNodePosition ( child , parent_idx ) ; this . setNodePosition ( parent , i ) ; i = parent_idx ; } } } private orderCorrect ( obj_a , obj_b ) { let obj_a_pr = this . _evalPriority ( obj_a ) ; let obj_b_pr = this . _evalPriority ( obj_b ) ; if ( this . _mode === BinaryHeapMode . MIN ) { return obj_a_pr <= obj_b_pr ; } else { return obj_a_pr >= obj_b_pr ; } } param obj param pos private setNodePosition ( obj , pos ) { if ( obj == null || pos == null || pos !== ( pos | 0 ) ) { throw new Error ( "minium required arguments are obj and new_pos" ) ; } let pos_obj = { score : this . evalInputScore ( obj ) , position : pos , } ; let obj_key = this . evalInputObjID ( obj ) ; this . _positions [ obj_key ] = pos_obj ; } /**
     *
     */ private getNodePosition ( obj ) { let obj_key = this . evalInputObjID ( obj ) ; let occurrence = this . _positions [ obj_key ] ; return occurrence ? occurrence . position : null ; } param obj returns { number } private removeNodePosition ( obj ) { let obj_key = this . evalInputObjID ( obj ) ; delete this . _positions [ obj_key ] ; } } export { BinaryHeap } ;