Min and Max Heap

BinaryTree_Heap.js

/*
const heap = new BinaryHeap( IsMinCompare );

heap.add( 5 );
heap.add( 8 );
heap.add( 6 );
heap.add( 9 );
heap.add( 13 );
heap.add( 3 );
heap.add( 1 );

for( let i=0; i < heap.length; i++ ){
    heap.items[ i ] -= 4;
}

while( heap.length > 0 && heap.items[ 0 ] <= 0 ){
    heap.remove();
}

console.log( heap.items );
*/

function IsMaxCompare( a, b ){ return ( a > b ); }
function IsMinCompare( a, b ){ return ( a < b ); }

class BinaryHeap{
    // #region MAIN
    compare = null;
    items   = [];

    constructor( fnCompare = IsMaxCompare ){
        this.compare = fnCompare;
    }
    // #endregion

    // #region GETTERS
    get length(){ return this.items.length; }
    // #endregion

    // #region METHODS
    add( n ){
        const idx = this.items.length;
        this.items.push( n );

        console.log( '-----------------' );
        if( idx !== 0 ) this.bubbleUp( idx );
        return this;
    }

    remove( idx=0 ){
        if( this.items.length === 0 ) return this;

        // We remove an item by swopping it with the LAST
        // item on the list.
        const i           = this.items.length - 1;  // Last Index
        const lastItem    = this.items.pop();       // Remove Last Item
        if( idx === i ) return this;                // We want to delete last item, we're done.

        // If NOT removing the last item, then place the last item
        // in the spot that we want to delete. From there bubble down
        // the item so its placed properly in the tree.
        this.items[ idx ] = lastItem;
        this.bubbleDown( idx );
        return this;
    }
    // #endregion

    // #region SHIFTING
    bubbleDown( idx ){
        const ary = this.items;
        const len = ary.length; // Used for bound checking
        const itm = ary[ idx ]; // Item being moved around
        let   lft = 0;          // Index to LEFT Child
        let   rit = 0;          // Index to RIGHT Child
        let   mov = -1;         //

        while( idx < len ){
            // Compute Children Indices
            lft = idx * 2 + 1;
            rit = idx * 2 + 2;
            mov = -1;

            // Check if item should be moved to its LEFT child position
            if( lft < len && this.compare( ary[lft], itm ) ) mov = lft;

            // Check if item should be moved to its RIGHT child position
            // if already moving to LEFT child, check if RIGHT is the
            // better position based on Min/Max Compare
            if( rit < len && this.compare( ary[rit], itm ) ){
                if( mov === -1 || this.compare( ary[rit], ary[lft] ) ) mov = rit;
            }

            // If item isn't suitable for either LEFT or RIGHT position, we're done.
            if( mov === -1 ) break;

            [ ary[idx], ary[mov] ] =   // Swop
            [ ary[mov], ary[idx] ];

            idx = mov;  // Save for next iteration
        }
        return this;
    }

    // Will move item up the tree by swopping with it's parent if
    // conditions are met.
    bubbleUp( idx ){
        const ary = this.items;
        let pidx;

        while( idx > 0 ){
            pidx = Math.floor( ( idx-1 ) / 2 );
            if( !this.compare( ary[ idx ], ary[ pidx ] ) ) break;
            
            [ ary[idx], ary[pidx] ] =   // Swop
            [ ary[pidx], ary[idx] ];

            idx = pidx;                 // Move up for next iteration
        }

        return this;
    }
    // #endregion
}