大顶堆

题目

群里有个人发的，题目很简单

随手写的

//debug print
function DB(obj) {  
//    console.log(obj);
}

//debug print maxHeap
function DBPMH(maxHeap) {  
    if(!maxHeap || MaxHeap != maxHeap.constructor) {
        DB("DBPMH the input is not MaxHeap");
        return;
    }
    let arr = maxHeap.arr;
    let len = maxHeap.len;

    DB("  \tlen is " + len);
    for(let i = 0;i < len;i++) {
        DB("  \t\tthe index " + i + " is " + arr[i]);
    }
}


//define MaxHeap
let MaxHeap = function() {  
    this.len = 0;
    this.arr = [];
}


MaxHeap.prototype.popMax = function() {  
    if(!this.len)
        return undefined;

    let value = this.arr[0];
    let arr = this.arr;

    let len = --this.len;
    arr[0] = this.arr[len];
    let index = 0;
    let maxIndex = len - 1;


    DB("pop the num = " + value + ", len = " + len + ", index = " + index + ", maxIndex = " + maxIndex);

    while(1) {
        let son1 = 2 * index + 1 <= maxIndex ? 2 * index + 1 : null;
        let son2 = 2 * index + 2 <= maxIndex ? 2 * index + 2 : null;
        let sonIndex = null;

        if(null === son1 && null === son2)
            return value;

        if(null === son1 && null !== son2) {
            sonIndex = 2 * index + 2;
        } else if(null !== son1 && null === son2) {
            sonIndex = 2 * index + 1;
        } else {
            sonIndex = son1 > son2 ? 2 * index + 1 : 2 * index + 2;
        }

        arr[sonIndex] ^= arr[index];
        arr[index] ^= arr[sonIndex];
        arr[sonIndex] ^= arr[index];
        index = sonIndex;
    }

    return value;
}

MaxHeap.prototype.push = function() {  
    if(1 !== arguments.length) {
        return undefined;
    }
    if("number" !== typeof(arguments[0])) {
        return undefined;
    }

    let arr = this.arr;
    arr[this.len++] = arguments[0];
    let len = this.len;
    let index = len - 1;

    DB("push the num = " + arguments[0] + ", len = " + len + ", index = " + index);

    while(1) {
        if(0 == index) 
            return true;

        let parentIndex = parseInt((index - 1) / 2);

        if(arr[parentIndex] > arr[index])  
            return true;

        arr[parentIndex] ^= arr[index];
        arr[index] ^= arr[parentIndex];
        arr[parentIndex] ^= arr[index];       
        index = parentIndex;
    }
    return true;
}



let maxHeap = new MaxHeap();  
maxHeap.push(1);  
maxHeap.push(6);  
DBPMH(maxHeap);

maxHeap.push(3);  
DBPMH(maxHeap);


maxHeap.popMax();  
maxHeap.push(5);

let len = maxHeap.len;  
for(let i = 0;i < len;i++) {  
    console.log(maxHeap.popMax());
}