Skip to content

Instantly share code, notes, and snippets.

@ramsunvtech
Last active October 16, 2020 19:41
Show Gist options
  • Save ramsunvtech/ae69cb82a1b48171f94c to your computer and use it in GitHub Desktop.
Save ramsunvtech/ae69cb82a1b48171f94c to your computer and use it in GitHub Desktop.
Heap Sort in Javascript
function heapSort(arr){
var len = arr.length,
end = len-1;
heapify(arr, len);
while(end > 0){
swap(arr, end--, 0);
siftDown(arr, 0, end);
}
return arr;
}
function heapify(arr, len){
// break the array into root + two sides, to create tree (heap)
var mid = Math.floor((len-2)/2);
while(mid >= 0){
siftDown(arr, mid--, len-1);
}
}
function siftDown(arr, start, end){
var root = start,
child = root*2 + 1,
toSwap = root;
while(child <= end){
if(arr[toSwap] < arr[child]){
swap(arr, toSwap, child);
}
if(child+1 <= end && arr[toSwap] < arr[child+1]){
swap(arr, toSwap, child+1)
}
if(toSwap != root){
swap(arr, root, toSwap);
root = toSwap;
}
else{
return;
}
toSwap = root;
child = root*2+1
}
}
function swap(arr, i, j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
@ThunderGit
Copy link

ThunderGit commented Oct 16, 2020

The sort works poorly on longer arrays.

For example:

heapSort([3,-12,6,1,2,-9,-100,100,12,0,0,-1,2,7,4]);
heapSort([17,1,11,5,4,5,4,0,2,7,8]);
heapSort([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]);
heapSort([12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]);
heapSort([39,-100,0,3,4,3,5,14,15,-12,-14,15,15-7,7,1,12,9,-8,5,12]);

Return

[ -100, -12, -9, 2, 2, 6, 1, 12, 0, 0, -1, 3, 4, 7, 100]
[0, 1, 2, 5, 5, 4, 4, 7, 8, 11, 17]
[1, 2, 3, 19, 4, 13, 5, 17, 6, 11, 7, 12, 8, 14, 9, 16, 10, 18, 15, 20]
[1, 2, 11, 13, 6, 8, 3, 10, 9, 4, 5, 7, 12, 14, 15]
[-100, -14, -12, 12, 0, 7, 3, 14, 4, -8, 3, 8, 5, 1, 12, 9, 5, 15, 15, 39]

Instead of

[-100, -12, -9, -1, 0, 0, 1, 2, 2, 3, 4, 6, 7, 12, 100]
[0, 1, 2, 4, 4, 5, 5, 7, 8, 11, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[-100, -14, -12, -8, 0, 1, 3, 3, 4, 5, 5, 7, 8, 9, 12, 12, 14, 15, 15, 39]

Here's an example of right JS Heap Sort (Maybe not ES6 style, but it works):
https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#JavaScript

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment