class Heap { type : string ; value : number [ ] ; constructor ( type ) { this . type = type ; this . value = [ ] ; } public create ( numbers ) { this . value = numbers ; const length = this . value . length ; for ( let i = Math . floor ( ( length / 2 ) - 1 ) ; i >= 0 ; i -- ) { this . adjust ( i , length ) ; } } public adjust ( index , length ) { const array = this . value ; for ( let i = 2 * index + 1 ; i < length ; i = 2 * i + 1 ) { if ( i + 1 < length ) { if ( ( this . type === 'max' && array [ i + 1 ] > array [ i ] ) || ( this . type === 'min' && array [ i + 1 ] < array [ i ] ) ) { i ++ ; } } if ( ( this . type === 'max' && array [ index ] < array [ i ] ) || ( this . type === 'min' && array [ index ] > array [ i ] ) ) { [ array [ index ] , array [ i ] ] = [ array [ i ] , array [ index ] ] ; index = i ; } } } /**
     * 堆属于优先队列，只能从末尾添加
     * 添加后有可能破坏堆的结构，需要从下到上进行调整
     * 如果元素小于父元素，向上置换
     *
     */ public add ( item ) { const array = this . value ; array . push ( item ) ; if ( array . length > 1 ) { let index = array . length - 1 ; let target = Math . floor ( ( index - 1 ) / 2 ) ; while ( target >= 0 ) { if ( ( this . type === 'min' && array [ index ] < array [ target ] ) || ( this . type === 'max' && array [ index ] > array [ target ] ) ) { [ array [ index ] , array [ target ] ] = [ array [ target ] , array [ index ] ] ; index = target ; target = Math . floor ( ( index - 1 ) / 2 ) ; } else { break ; } } } } /**
     * 由于堆属于优先队列，因此从头部移除
     * 移除后，末尾元素填充头部，开始从头部进行下沉操作
     */ public pop ( ) { const array = this . value ; let result = null ; if ( array . length > 1 ) { result = array [ 0 ] ; array [ 0 ] = array . pop ( ) ; this . adjust ( 0 , array . length ) ; } else if ( array . length === 1 ) { return array . pop ( ) ; } return result ; } } export default Heap ;