SOURCE

class MinHeap {
    constructor(compareFn = defaultCompare){
        this.compareFn = compareFn;
        this.heap = [];
    }
    getLeftIndex(index){
        return 2 * index + 1;
    }
    getRightIndex(index){
        return 2 * index + 2;
    }
    getParentIndex(index){
        if(index === 0){
            return undefined;
        }
        return index / 2;
    }
    insert(value){
        if(value != null){
            this.heap.push(value);
            this.siftUp(this.heap.length - 1);
            return true;
        }
        return false;
    }
    siftUp(index){
        let parent = this.getLeftIndex(index);
        while(index > 0 && this.compareFn(this.heap[parent],this.heap[index]) > Compare.BIGGER_THAN){
            swap(this.heap,parent,index);
            index = parent;
            parent = this.getParentIndex(index);
        }
    }
    size(){
        return this.heap.length;
    }
    isEmpty(){
        return this.size() === 0;
    }
    findMinimum(){
        return this.isEmpty()?undefined : this.heap[0];
    }
    extract(){
        if(this.isEmpty()){
            return undefined
        }
        if(this.size() === 1){
            return this.heap.shift();
        }

        const removedValue = this.heap.shift();
        this.siftDown(0);
        return removedValue;
    }
    siftDown(index){
        let element = index;
        const left = this.getLeftIndex(index);
        const right = this.getRightIndex(index);
        const size = this.size();

        if(left < size && this.compareFn(this.heap[element],this.heap[index] === Compare.BIGGER_THAN)){
            element = left;
        }

        if(right < size && this.compareFn(this.heap[element],this.heap[right]) === Compare.LESS_THAN){
            element = right;
        }

        if(index !== element){
            swap(this.heap,index,element);
            this.siftDown(element);
        }


    }
}


class MaxHeap extends MinHeap{
    constructor(compareFn = defaultCompare){
        super(compareFn);
        this.compareFn = reverseCompare(compareFn);
    }
}

const Compare = {
    LESS_THAN : -1,
    BIGGER_THAN : 1
}

function defaultCompare(a,b){
    if(a === b){
        return 0;
    }

    return a < b?Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array,a,b){
    const tmp = array[a];
    array[a] = array[b];
    array[b] = tmp;
}  

function reverseCompare(compareFn){
    return (a,b) => compareFn(b,a);
}

//堆排序算法

function heapSort(array,compareFn = defaultCompare){
    let heapsize = array.length;
    buildMaxHeap(array,compareFn);
    while(heapsize > 1){
        swap(array,0,--heapsize);
        heapify(array,0,heapsize,compareFn);
    }
    return array;
}

function buildMaxHeap(array,compareFn){
    for(let i = Math.floor(array.length / 2);i > 0;i -= 1){
        heapify(array,i,array.length,compareFn)
    }
    return array;
}

// const swap = (array,a,b) => [array[a],array[b]] = [array[b],array[a]];

const heap = new MinHeap();

for(let i = 1;i < 10;i++){
    heap.insert(i);
}

console.log(heap.extract())

const maxheap = new MaxHeap();

maxheap.insert(2)
maxheap.insert(3)
maxheap.insert(4)
maxheap.insert(5)
maxheap.insert(1)

console.log(maxheap.size())
console.log(maxheap.findMinimum())