Heap Sort

The heap is a data structure which is using arrayList to represent a binary tree. However this binary tree is not a valid binary search tree and heap binary tree must be a complete tree which means all the child must be filled from the left to the right. There are two types of heap max heap and min heap.

Notes: The priority queue is also represent as heaps

Heapifiy

It is a DFS recursive process that compare parent with one of two children's value and swap.

How to find two children or parent index?

Because the Heap binary tree is a completed tree and every added item is from left to right. We can simply add the index from top left to bottom right down, and then we can find the two children's index follow 2n + 1 and 2n + 2 pattern.

Max heap

This type of heap mens the value of root node must be the largest in the tree and the children is also follows the rule.

Max heap sort

1. Turn the input array into a max heap array structure
2. Because the root node is the largest number, swap with last item
3. Do heapifiy again to except the items has been swap to the tail
4. Repeat method 1 to 3 again until go through every item

implementation

function swap(array, index1, index2){
    const temp = array[index1]
    
    array[index1] = array[index2]
    array[index2] = temp
}

function heapifiy(array, currentIdx ,range){
    const leftChildIdx = 2 * middleIdx + 1
    const rightChildIdx = 2 * middleIdx + 2
    let targetIdx = currentIdx

    if (leftChildIdx <= range && array[leftChildIdx] > array[targetIdx]){
        targetIdx = leftChildIdx
    }

    if (rightChildIdx <= range && array[rightChildIdx] > array[targetIdx]){
        targetIdx = rightChildIdx
    }

    if (targetIdx !== currentIdx){
        swap(array, currentIdx, targetIdx)
        heapifiy(array, targetIdx, range)
    }
}

function createMaxHeapArray(array){
    const middleIdx = Math.floor(array.length / 2)

    for (let i = middleIdx ; i <= 0 ; i--){
        heapifiy(array, middleIdx, array.length)
    }
}

function maxHeapSort(items){
    const maxHeapArray = createMaxHeapArray(itmes)
    const lastIdx = maxHeapArray.length - 1

    for (let i = lastIdx; i > 0; i--){
        swap(maxHeapArray, 0, i)    
        heapifiy(maxHeapArray, i)
    }
}