Why doesn't my heap sort function work as expected?

user_11422407 0
Viewed 90

I want to implement heap sort using JS, but the result is incorrect (it is not sorted). I think my logic is correct. However, I cannot figure out what is wrong in the code. Could anyone help me with this?

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function buildHeap(arr) {
    const n = arr.length;
    for (let i = Math.floor((n - 1) / 2); i >= 0; i--){
        heapify(arr, n, i);
    }
}

function heapify(arr, n, i) {
    let left = 2 * i + 1,
        right = 2 * i + 2,
        max = i;
    
    if (i < n && arr[left] > arr[max]) {
        max = left;
    }
    if (i < n && arr[right] > arr[max]) {
        max = right;
    }
    if (max != i) {
        swap(arr, i, max);
        heapify(arr, n, max);
    }
}

function heapSort(arr) {
    let n = arr.length;
    buildHeap(arr);
    for (let i = n - 1; i >= 0; i--){
        swap(arr, 0, i);
        n--;
        heapify(arr, n, 0);
    }
    console.log(arr);
    return arr;
}
let tmp = [32,4,231,42,2,6,6,7,11];
heapSort(tmp);

As you can see the output is:

[231, 42, 7, 6, 2, 11, 32, 6, 4]

while I expected:

[2, 4, 6, 6, 7, 11, 32, 42, 231]
data-structures algorithm javascript
1 Answers

The problem is in this piece of code:

if (i < n && arr[left] > arr[max]) {
    max = left;
}
if (i < n && arr[right] > arr[max]) {
    max = right;
}

The check should not be made with i, but with the index that you are about to use:

if (left < n && arr[left] > arr[max]) {
    max = left;
}
if (right < n && arr[right] > arr[max]) {
    max = right;
}
user_54598390
Related