Skip to content

Instantly share code, notes, and snippets.

@ungarson
Created March 20, 2019 08:25
Show Gist options
  • Save ungarson/867ed3b072809ded77b06f251b62ea05 to your computer and use it in GitHub Desktop.
Save ungarson/867ed3b072809ded77b06f251b62ea05 to your computer and use it in GitHub Desktop.
Heap sort in js
function maxHeapify(arr, i) {
const l = i * 2 + 1;
const r = i * 2 + 2;
let largest;
if (l <= arr.heapSize && arr[l] > arr[i]) {
largest = l;
} else largest = i;
if (r <= arr.heapSize && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
maxHeapify(arr, largest);
}
}
function buildMaxHeap(arr) {
arr.heapSize = arr.length - 1;
for (let i = parseInt((arr.length - 2)/2); i >= 0; i--) {
maxHeapify(arr, i);
}
}
function heapSort(arr) {
buildMaxHeap(arr);
for (let i = arr.length - 1; i >= 1; i--) {
let temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
arr.heapSize = arr.heapSize - 1;
maxHeapify(arr, 0);
}
return arr;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment