Interview question: javascript implement heap sort

heapSort.js

/**
 * From: https://leetcode.com/problems/sort-an-array/
 * Question: heap sort
 * heap is Complete Binary Tree, it has complete binary tree
* @param nums
 */
var sortArray = (nums) => {
    var swap = (i, j) => {
        var tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp
    }
    var numsLen = nums.length
    /**
     * std name is maxHeapify(use algorithm Max-Heapify), but I like call maxHeapify
     * @param i
     * @param heapLen heapLen to get whole heap arr or subHeap(heap arr with heapLen)
     */
    var maxHeapify = (i, heapLen) => {
        var isLeaf = (i) => {
            // this node has no leaf in this sub heap(attention is sub heap determine by heapLen , it means this node in subHeap is leaf node)
            return 2 * i + 1 >= heapLen
        }
        while (true) {
            if (isLeaf(i)) {
                break
            }
            /**
             * why following code only compare left child node value and right child node value, but ignore left child tree and right child tree more deep node value?
             * since heap sort is from tree downside(last item) to root, node's left child tree and right child tree has put their max node to child tree root
             */
            var l = 2 * i + 1
            var r = 2 * i + 2
            var nextI
            if (r >= heapLen || nums[l] > nums[r]) {
                nextI = l
            } else {
                nextI = r
            }
            if (nums[nextI] > nums[i]) {
                swap(nextI, i)
            }
            i = nextI
        }
    }
    var heapSort = () => {
        for (var i = numsLen - 1; i >= 0; i--) {
            maxHeapify(i, numsLen)
        }
        for (var i = numsLen - 1; i >= 0; i--) {
            swap(0, i)
            // above code move max to idx i, the next iteration need max subHeap len i - 1 + 1, so use following max subHeap
            maxHeapify(0, i)
        }
    }
    heapSort()
    return nums
}
var {assertSort} = require("./sortHelper")
var asrSort = (nums) => {
    assertSort(sortArray, nums)
}
describe("heapSort", () => {
    it("1", () => {
        asrSort([3, 2, 1])
    })
    it("2", () => {
        asrSort([5, 2, 3, 1])
    })
})

If you like my article, donate me a coffee and let me continue

Donate

Donate backup