max_binary_heap.js

class MaxHeap {
    constructor (arr) {
        this.heap = arr
        
        for (let i = Math.round(this.heap.length/2); i >= 0; i--) {
            this.heapify(i)
        }
    }
    
    heapify(i) {
        const children = [
            this.getLeftChildIndex(i),
            this.getRightChildIndex(i)
        ]
        
        children.forEach(child => {
            if (child !== -1 && this.heap[child] > this.heap[i]) {       
                let tmp = this.heap[i]
                this.heap[i] = this.heap[child]
                this.heap[child] = tmp
                this.heapify(child)
            }
        })
    }
    
    getParentIndex (i) {
        return i > 0 ? Math.floor((i+1)/2) - 1: -1
    }
    
    getLeftChildIndex (i) {
        let index = 2*i + 1
        return index < this.heap.length ? index : -1
    }

    getRightChildIndex (i) {
        let index = 2*i + 2
        return index < this.heap.length ? index : -1
    }

    insert (el) {
        this.heap.push(el)
        
        const bubbleUp = (i) => {
            const parent = this.getParentIndex(i)
            if (parent !== -1 && this.heap[i] > this.heap[parent]) {
                let tmp = this.heap[i]
                this.heap[i] = this.heap[parent]
                this.heap[parent] = tmp
                bubbleUp(parent)
            }
        }
        
        bubbleUp(this.heap.length - 1)
    }
    
    get length () {
        return this.heap.length
    }
        
    extractTop () {
        if (this.heap.length === 1) {
            return this.heap.pop()
        }
        
        const top = this.heap[0]
        const newTop = this.heap.pop()
        
        this.heap[0] = newTop
        this.heapify(0)
        
        return top
    }
}