Heapsort Implementation in JavaScript

programming
1

I’m working on my next tutorial that describes how heapsort works, but who knows when I’ll actually finish it! In the meantime, here is my heapsort implementation in JavaScript:

var arrayLength;

function buildHeap(input) {
    arrayLength = input.length;

    for (var i = Math.floor(arrayLength / 2); i >= 0; i -= 1) {
        heapify(input, i);
    }
}

function heapify(input, i) {
    var left = 2 * i + 1;
    var right = 2 * i + 2;
    var largest = i;

    if (left < arrayLength && input[left] > input[largest]) {
        largest = left;
    }

    if (right < arrayLength && input[right] > input[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(input, i, largest);
        heapify(input, largest);
    }
}

function swap(input, index_A, index_B) {
    var temp = input[index_A];

    input[index_A] = input[index_B];
    input[index_B] = temp;
}

function heapSort(input) {
    buildHeap(input);

    for (var i = input.length - 1; i > 0; i--) {
        swap(input, 0, i);
        arrayLength--;
        heapify(input, 0);
    }
}

var example = [40, 10, 50, 24, 1, 2, 4, -10, 15, 7, 8, 5];
heapSort(example);
console.log(example); // -10,1,2,4,5,7,8,10,15,24,40,50

Hopefully this is useful for somebody :stuck_out_tongue:

Cheers,
Kirupa

2

I don’t know if it’s the algorithm or your implementation, but I have a less clear reading of this code than I did of your merge sort code. (Well, I can see that it’s sorting stuff, but it doesn’t invoke the concept of a ‘heap’ to me.)

(Finally have a non-cellular home internet connection again, BTW. I’ve been missing one for a month so I haven’t been posting as much.)

3

Fair point! I will need to elaborate on what heaps are, how they are represented in arrays, and how the heapify function does what you need it to do :smile:

4

Interesting; I just wikipedia-ed heap and saw my confusion:

A heap data structure should not be confused with the heap which is a common name for the pool of memory from which dynamically allocated memory is allocated. The term was originally used only for the data structure.

Note that despite the similarity of the name “heap” to “stack” and “queue”, the latter two are abstract data types, while a heap is a specific data structure, and “priority queue” is the proper term for the abstract data type.

I think the dynamic memory space is such a more common definition / usage these days that I completely forgot about the data structure definition. To me, a ‘heap’ isn’t organized as the tree-structured priority-queue that apparently heapsort refers to… if I throw my clothes into a heap on the floor, the definition matches the dynamic memory space definition much more than the priority queue definition.

(It might not make sense to address the two different definitions of heap in your tutorial; I only have a default definition of heap via the copious amounts of systems / OS classes I apparently took.)

5

It looks very similar to this:
// http://stackoverflow.com/questions/29292558/heapsort-not-working-in-javascript

If all you wanna do is sort numbers though, who gives a heap of @#$ about all that? :smile:

var example = [40, 10, 50, 24, 1, 2, 4, -10, 15, 7, 8, 5]; 
function sortNum(a,b) {
    return a - b;
}
alert(example.sort(sortNum)); // -10,1,2,4,5,7,8,10,15,24,40,50
1 Like