0004: Algorithm — heap sort

algorithm

Heap sort is sorted using the characteristics of the data structure heap

Note: Heap a tree with leaves down, root is always the smallest, root< left child &root< right child

Time complexity

Heap time complexity: O(nlogn)O(nlogn)O(nlogn)

Heap out time complexity: O(nlogn)O(nlogn)O(nlogn)

Overall time complexity: O(nlogn)O(nlogn)O(nlogn)

js

const input = [4.2.15.2.5.6.21.67.2.3]

const heapAdd = (roots, val) = > {
    const childs = [];
    let node = null;
    const notadded = roots.every(root= > {
        if(! root.left) { root.left = { val,parent: root,
            }
            node = root.left
            return false;
        }
        if(! root.right) { root.right = { val,parent: root,
            }
            node = root.right
            return false;
        }
        childs.push(root.left)
        childs.push(root.right)
        return true
    })
    if (notadded) {
        return heapAdd(childs, val)
    }
    return node
}

const heapSort = (node) = > {
    if(! node.parent)return;
    if (node.val < node.parent.val) {
        const temp = node.parent.val
        node.parent.val = node.val
        node.val = temp
        heapSort(node.parent)
    }
}

const heapDown = (root) = > {
    if(! root)return;
    const right = root.right;
    let node = root.left;
    if (right && node && right.val < node.val) {
        node = right;
    }
    if (node && node.val < root.val) {
        const temp = node.val
        node.val = root.val
        root.val = temp
        heapDown(node)
    }
    
}

const getRight = (root) = > {
    if(! root)return root;
    if(! root.left && ! root.right)return root
    if (root.right) return getRight(root.right);
    return getRight(root.left)
}

const heapPop = (root) = > {
    const temp = root.val;
    const left = root.left;
    const right = root.right;
    if(! left && ! right)return temp;
    const final = getRight(root);
    if (final) {
        root.val = final.val
        const finalParent = final.parent
        if (finalParent && finalParent.right === final) {
            finalParent.right = null;
        } else if (finalParent && finalParent.left === final) {
            finalParent.left = null;
        }

        heapDown(root)
        return temp
    }
    return temp;
}

const sort = (arr) = > {
    const root = { val : arr[0]}
    for(let i = 1; i < arr.length; i++) {
       const node = heapAdd([root], arr[i]) 
       heapSort(node)
       final = node;
    }
    for (let i = 0; i < arr.length; i++) {
        arr[i] = heapPop(root);
    }
    return arr;
}
console.log(sort(input))
Copy the code