Skip to content

Instantly share code, notes, and snippets.

@gyoshev
Created November 8, 2012 13:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • 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);
@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