Skip to content

Instantly share code, notes, and snippets.

@chasingmaxwell
Last active October 16, 2020 21:10
Show Gist options
  • Save chasingmaxwell/3a293f044543bb23d68861f9e8178fa8 to your computer and use it in GitHub Desktop.
Save chasingmaxwell/3a293f044543bb23d68861f9e8178fa8 to your computer and use it in GitHub Desktop.
Implementation of heapsort in JavaScript.
// Implementation of heapsort in JavaScript.
LENGTH = 1e2;
MAX = 2e4;
MIN = 1;
function generateInput(min, max, length) {
const res = [];
while (res.length < length) {
res.push(Math.round(Math.random() * (max - min) + min));
}
return res;
}
function getParent(i) {
return i >> 1;
}
function getLeft(i) {
return i << 1;
}
function getRight(i) {
return (i << 1) + 1;
}
function maxHeapify(heap, i) {
const l = getLeft(i);
const r = getRight(i);
let largest = i;
if (l && l <= heap.heapSize && heap[l] > heap[i]) {
largest = l;
}
if (r && r <= heap.heapSize && heap[r] > heap[largest]) {
largest = r;
}
if (largest !== i) {
const oldI = heap[i];
heap[i] = heap[largest];
heap[largest] = oldI;
maxHeapify(heap, largest);
}
}
function buildMaxHeap(input) {
input.heapSize = input.length - 1;
for (let i = Math.floor((input.length - 1) / 2); i > 0; i--) {
maxHeapify(input, i);
}
}
function heapSort(input) {
// fill the 0 index so we can start from 1 (we need this because math).
input.unshift(null);
buildMaxHeap(input);
for (i = input.length - 1; i > 1; i--) {
const first = input[1];
input[1] = input[i];
input[i] = first;
input.heapSize = input.heapSize - 1;
maxHeapify(input, 1);
}
// Remove that first item.
input.shift();
}
const input = generateInput(MIN, MAX, LENGTH);
heapSort(input);
console.log(input);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment