js 데이터 구조 구현 - 더미 (최대 더미)

/**
 *        
 * @class
 * @param {Array} [initDataArray]      
 * @param {number} [maxSize=9999]       
 */
 /**
*  i=0，  i    ，    i     (i-1)/2
*2*i+1        2*i+2     
*/
function MaxHeap(initDataArray, maxSize = 9999) {
    let arr=initDataArray || [];

    let currSize=arr.length;
 //  heap，        
    let heap=new Array(arr.length);

    function init() {

        for(let i=0; i<currSize;i++){
            heap[i]=arr[i];
        }
        //            
        let currPos=Math.floor((currSize-2)/2);
        while (currPos>=0){
			//          
            shif_down(currPos, currSize-1);
            //         
            currPos--;
        }

    }

    function shif_down(start,m) {
        //   
        let parentIndex=start,
            //    
            maxChildIndex=parentIndex*2+1;

        while (maxChildIndex<=m){
            if(maxChildIndex<m && heap[maxChildIndex]<heap[maxChildIndex+1]){
                //                 
                maxChildIndex=maxChildIndex+1;
            }
            if(heap[parentIndex]>=heap[maxChildIndex]){
                break;
            }else {
                //  
                let temp=heap[parentIndex];
                heap[parentIndex]=heap[maxChildIndex];
                heap[maxChildIndex]=temp;
                parentIndex=maxChildIndex;
                maxChildIndex=maxChildIndex*2+1
            }
        }
    }
    /**
     *       
     *
     * @param {*} data    
     * @returns {boolean} isSuccess         
     */
    this.insert = function (data) {
        //            
        if(currSize===maxSize){
            return false
        }

        heap[currSize]=data;
        shif_up(currSize);
        currSize++;
        return true;
    };

    function shif_up(start) {
        let childIndex=start;   //     
        let parentIndex=Math.floor((childIndex-1)/2); //   

        while (childIndex>0){
            //       
            if(heap[parentIndex]>=heap[childIndex]){
                break;
            }else {
                let temp=heap[parentIndex];
                heap[parentIndex]=heap[childIndex];
                heap[childIndex]=temp;
                childIndex=parentIndex;
                parentIndex=Math.floor((parentIndex-1)/2);
            }
        }
    }

    /**
     *      ，        
     *
     * @returns {*} data        
     */
    this.removeRoot = function () {
        if(currSize<=0){
            return null;
        }
        let maxValue=heap[0];
        heap[0]=heap[currSize];
        currSize--;
        shif_down(0, currSize-1);
        return maxValue;
    };

    init();

}

/**
 *          
 * @class
 * @param {*} data
 */
function BinaryTreeNode(data) {

    this.data = data;

    this.parent = null;

    this.leftChild = null;
    this.rightChild = null;

}

const maxHeap = new MaxHeap();

const initDataArray = [];
for (let index = 0; index < 5; index++) {

    const value = 5 + 95 * Math.random();

    if (-1 === initDataArray.indexOf(value)) {
        //      
        initDataArray.push(value);
        if (!maxHeap.insert(value)) {
            //     ，      
            index--;
        }
    } else {
        //    ，      
        index--;
    }

}
console.log('init array = ', initDataArray);


const max1 = maxHeap.removeRoot();
console.log('max1', max1);

const max2 = maxHeap.removeRoot();
console.log('max2', max2);

const max3 = maxHeap.removeRoot();
console.log('max3', max3);