maxheap.js

//maxHeapify time complexity O(logn)
//i starts from 1
const maxHeapify = (A, heapsize, i) => {
    let largest;
    let l = 2 * i
    let r = 2 * i + 1
    if (l <= heapsize && A[l - 1] > A[i - 1]) {
        largest = l
    } else {
        largest = i
    }
    if (r <= heapsize && A[r - 1] > A[largest - 1]) {
        largest = r
    }
    if (largest !== i) {
        let temp = A[i - 1]
        A[i - 1] = A[largest - 1]
        A[largest - 1] = temp
        maxHeapify(A, heapsize, largest)
    }
}

//buildMaxHeap time complexity O(n)
const buildMaxHeap = (A) => {
    const heapsize = A.length
    for (let i = Math.floor(heapsize / 2); i > 0; i--) {
        maxHeapify(A, heapsize, i)
    }
}

//heapExtractMax time complexity O(logn)
const heapExtractMax = (A) => {
    let heapsize = A.length
    if (heapsize < 1) {
        console.log('Error')
        return
    }
    const maximum = A[0]
    A[0] = A[heapsize - 1]
    A.splice(heapsize - 1, 1)
    heapsize = heapsize - 1
    maxHeapify(A, heapsize, 1)
    return maximum
}

//heapIncreaseKey time complexity O(logn)
//i starts from 1
const heapIncreaseKey = (A, i, key) => {
    if (key < A[i - 1]) {
        console.log("Enter higher value")
        return
    }
    A[i - 1] = key
    while (i > 1 && A[Math.floor(i / 2) - 1] < A[i - 1]) {
        let temp = A[i - 1]
        A[i - 1] = A[Math.floor(i / 2) - 1]
        A[Math.floor(i / 2) - 1] = temp
        i = Math.floor(i / 2)
    }
}

//heapDecreaseKey time complexity O(logn)
//i starts from 1
const heapDecreaseKey = (A, i, key) => {
    if (key > A[i - 1]) {
        console.log("Enter lesser value")
        return
    }
    A[i - 1] = key
    maxHeapify(A, A.length, i)
}

//heapInsert time complexity O(logn)
const heapInsert = (A, key) => {
    A.push(Number.NEGATIVE_INFINITY)
    heapIncreaseKey(A, A.length, key)
}

//heapsort time complexity O(nlogn)
const heapSort = (A) => {
    buildMaxHeap(A)
    let heapsize = A.length
    for (i = heapsize; i > 1; i--) {
        let temp = A[0]
        A[0] = A[heapsize - 1]
        A[heapsize - 1] = temp
        heapsize = heapsize - 1
        maxHeapify(A, heapsize, 1)
    }
}

const lst = [1, 14, 10, 8, 7, 9, 3, 2, 4, 6]
buildMaxHeap(lst)
console.log(lst)
let max = heapExtractMax(lst)
console.log(max, lst)