Mini-Heap Sort implementation in JavaScript

Question

I want to implement the heap sort algorithm in JavaScript using MinHeap. But the code output isn't correct.

My dataset had 1000 numbers and I'm trying to heapify all data.

import * as fs from 'fs';

// Read the input file
const input = fs.readFileSync('data.txt', 'utf8');
let data = input.split(" ").map(Number);

// Call the main function to build the min-heap and print the results
main(data);

// Min-heapify function
function heapify(data, i, n) {
    let left = 2 * i;
    let right = 2 * i + 1;
    let smallest = i;

    if (right <= n && left <= n && data[right] < data[left]) {
        if (data[right] < data[i]) {
            smallest = right;
        }
    }
    else (right <= n && left <= n && data[right] > data[left])
    {
        if (data[left] < data[i]) {
            smallest = left;
        }
    }
    //if smallest is changed to original left or right
    if (smallest != i) {
        // Swap data[i] and data[smallest]
        [data[i], data[smallest]] = [data[smallest], data[i]];

        //Recursively heapify the subtree
        heapify(data, smallest, n);
    }
    return data;
}

// Build min-heap function
function buildMinHeap(data) {
    const n = data.length - 1;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(data, i, n);
    }
}

// Main function
function main(data) {

    // Build a min-heap
    buildMinHeap(data);

    // Print the first 20 values data[1], data[2], ..., data[20]
    console.log("First 20 values:");
    const n = data.length;
    for (let i = 0; i <= 19 && i <= n; i++) {
        process.stdout.write(data[i] + ',');
    }

    console.log("Last 20 values:");
    for (let i = n - 1; i >= n - 20 && i >= 1; i--) {
        process.stdout.write(data[i] + ',');
    }
}

What's wrong with this code?

Answer 1

There are these issues in heapify:

• As arrays have 0 as the first index, the "formula" left = 2 * i is wrong; it would say that the left child of the root (at 0) is ... 0. You need left = 2 * i + 1 and right = 2 * i + 2.

• You have an else followed by comparison expression. That doesn't do what you think it does. You need else if

• The if ... else structure does not include what to do if the node has only a left child, i.e. when left == n. Currently your code then assumes that the smallest is at i, but you never check whether that is true.

In buildMinHeap there is this problem:

• The loop doesn't start at the correct index when the number of nodes is even. For instance, if you have 4 nodes, then n will be set to 3 and the loop will start at 0. This is wrong. It should start at 1, as 1 is the parent of the node at n.

Not a problem, but

• if you have right <= n then testing for left <= n is useless: if the first is true, then the second is guaranteed to be true too as left is one less than right.

• heapify should not have to return anything. The mutation happens in-place.

• Comments should not be saying trivial things like // Build min-heap function. This doesn't help the reader. Instead provide comments to explain the "why?".

Here is the correction for these two functions:

function heapify(data, i, n) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let smallest = i;

    // Check if left child has smaller value: if so, select it
    if (left <= n && data[left] < data[smallest]) {
        smallest = left;
    }
    // Check if right child has even smaller value: if so, select it
    if (right <= n && data[right] < data[smallest]) {
        smallest = right;
    }
    // If either child has the smallest value, swap and repeat
    if (smallest != i) {
        [data[i], data[smallest]] = [data[smallest], data[i]];
        heapify(data, smallest, n);
    }
}

function buildMinHeap(data) {
    const n = data.length - 1;
    // Iterate all *internal* nodes from bottom to top
    for (let i = Math.floor((n - 1) / 2); i >= 0; i--) {
        heapify(data, i, n);
    }
}

Finally, this is not an implementation of heap sort. This only builds the heap. A heap is not a sorted array, but a data structure that ensures the heap property. This can be useful for several algorithms, including heapsort. For implementing heapsort, you need to keep extracting the minimum from the heap until it is empty. You can save the extracted values in the part of the array that is no longer used by the shrinking heap.

Here is a function you could add to your code to accomplish that:

function heapSort(data) {
    // Turn the input data into a min-heap
    buildMinHeap(data);
    console.log(...data);
    // The sorted part will grow from the right end towards the left
    for (let n = data.length - 1; n > 0; n--) {
        // Move current heap-root to the sorted partition at the right
        [data[0], data[n]] = [data[n], data[0]];
        // The heap is now smaller and has a new value at its root: heapify it
        heapify(data, 0, n-1);
    }
}

You can call heapSort(data) from your main function.

Be aware though, that when you use a min-heap, then heapsort will sort in descending order. If you want the result to be sorted in ascending order, you should change your heap implementation into a max-heap.