| Heap-Sort |

Defination :
Heap sort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree. Once the data list has been made into a heap, the root node is guaranteed to be the largest (or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log n) time, instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time, and this is also the worst case complexity.

Performance
Best-case Time complexity: O(nlogn)
Average-case Time complexity: O(nlogn)
worst-case Time complexity: O(nlogn)

Space complexity
worst-case Space complexity: O(1)


        function heapSort(arr){

            async function max_heapify(a, i, length) {
                while (true) {
                    var left = i*2 + 1;
                    var right = i*2 + 2;
                    var largest = i;
    
                    if (left < length && a[left] > a[largest]) {
                            largest = left;
                    }
    
                    if (right < length && a[right] > a[largest]) {
                        largest = right;
                    }
    
                    if (i == largest) {
                        break;
                    }
    
                    await swapIndex(a, i, largest);
                    await drawArr(arr);
                    await sleep(time)
                    i = largest;
                    }
            }
    
            async function heapify(a, length) {
                for (var i = Math.floor(length/2); i >= 0; i--) {
                    await max_heapify(a, i, length);
                }
            }
    
            async function heapsort(a) {
                await heapify(a, a.length-1);
    
                for (var i = a.length - 1; i >= 0; i--) {
                        await swapIndex(a, i, 0);
                    await drawArr(arr);
                    await sleep(time)
                    await max_heapify(a, 0, i);
                }	
            }
    
            heapsort(Arr);
        }

Designed and built with by The ThunderBolt

Algo Visualizer

Heap sort