Skip to content

Instantly share code, notes, and snippets.

@gyoshev
Created November 8, 2012 13:36
Show Gist options
  • Save gyoshev/4038839 to your computer and use it in GitHub Desktop.
Save gyoshev/4038839 to your computer and use it in GitHub Desktop.
Heap sort in javascript
var a = [ 9, 10, 2, 1, 5, 4, 3, 6, 8, 7, 13 ];
function swap(a, i, j) {
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
function max_heapify(a, i, length) {
while (true) {
var left = i*2 + 1;
var right = i*2 + 2;
var largest = i;
if (left < length && a[left] > a[largest]) {
largest = left;
}
if (right < length && a[right] > a[largest]) {
largest = right;
}
if (i == largest) {
break;
}
swap(a, i, largest);
i = largest;
}
}
function heapify(a, length) {
for (var i = Math.floor(length/2); i >= 0; i--) {
max_heapify(a, i, length);
}
}
function heapsort(a) {
heapify(a, a.length);
for (var i = a.length - 1; i > 0; i--) {
swap(a, i, 0);
max_heapify(a, 0, i-1);
}
}
heapsort(a);
@SuperPaintman
Copy link

https://gist.github.com/gyoshev/4038839#file-heapsort-js-L44

-        max_heapify(a, 0, i-1);
+        max_heapify(a, 0, i);

@zirho
Copy link

zirho commented Aug 10, 2017

I believe line # 33 should be for (var i = Math.floor(length/2 - 1); i >= 0; i--) { to avoid one excessive child check.

@Dellybro
Copy link

Dellybro commented Sep 14, 2017

This doesn't work.

To be specific my array ends up being

[ 1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 13 ]

and when debugging it i'm realizing the largest isn't always correct

left: 5, right: 6, largest: 5

@smilingkite
Copy link

I too see the outcome that @Dellybro sees. @SuperPaintman's fix solves the test case included, I'm not sure it's enough to fix the algo though.

@shuch
Copy link

shuch commented Jun 9, 2020

a = [5, 4, 3, 2, 1];
heapsort(a);
console.log(a);// 1, 3, 2, 4, 5

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