Skip to content

Instantly share code, notes, and snippets.

@nodew
Created February 28, 2019 05:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nodew/7c09c12cd680365498a80e280e785441 to your computer and use it in GitHub Desktop.
Save nodew/7c09c12cd680365498a80e280e785441 to your computer and use it in GitHub Desktop.
heapSort implementation in javascript
function heapify(array, index, heapSize, cmp) {
let left = 2 * index + 1;
let right = 2 * index + 2;
let largest = index;
if (left < heapSize && cmp(array[left], array[index]) > 0) {
largest = left;
}
if (right < heapSize && cmp(array[right], array[largest]) > 0) {
largest = right;
}
if (largest !== index) {
swapArrayItem(array, largest, index);
heapify(array, largest, heapSize, cmp);
}
}
const swapArrayItem = (arr, i, j) => {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
};
function buildMaxHeap(array, cmp) {
for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
heapify(array, i, array.length, cmp);
}
return array;
}
function comparator(a, b) {
return a - b;
}
function heapSort(array, cmp = comparator) {
cmp = cmp;
let size = array.length;
buildMaxHeap(array, cmp);
for (let i = array.length - 1; i > 0; i -= 1) {
swapArrayItem(array, 0, i);
size -= 1;
heapify(array, 0, size, cmp);
}
return array;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment