Skip to content

Instantly share code, notes, and snippets.

@claytonjwong
Last active March 9, 2021 20:50
Show Gist options
  • Save claytonjwong/2bcf514e89f7d0950be362d2021969ff to your computer and use it in GitHub Desktop.
Save claytonjwong/2bcf514e89f7d0950be362d2021969ff to your computer and use it in GitHub Desktop.
/*
Heap Property:
* MinHeap: For every object x, the key of x is <= the keys of its children
* MaxHeap: For every object x, the key of x is >= the keys of its children
----------------------------------------------------------------------------------------------------
Insert:
1. Add object x onto the end of the array and increment the array size
2. Repeatedly swap the object x and the parent of x while there is a heap violation
----------------------------------------------------------------------------------------------------
Extract(Min/Max):
1. Store the value of the first item at index 0 to be returned
2. Set the value of the first item at index 0 to the last item of the array and decrement the array size
3. Repeatedly swap the object x and the min/max child of x while there is a heap violation
4. Return the value of the first item stored in step 1
*/
let key = x => Array.isArray(x) ? x[0] : x;
let heappush = (A, x, f = Math.min) => {
let P = i => Math.floor((i - 1) / 2); // parent
A.push(x);
let N = A.length,
i = N - 1;
while (0 < i && key(A[i]) == f(key(A[i]), key(A[P(i)]))) {
[A[i], A[P(i)]] = [A[P(i)], A[i]];
i = P(i);
}
};
let heappop = (A, f = Math.min) => {
let L = i => 2 * i + 1, // children
R = i => 2 * i + 2;
let N = A.length,
i = 0;
let top = A[0];
[A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N;
let ok;
do {
ok = true;
let left = f == Math.min ? Infinity : -Infinity,
right = left;
if (L(i) < N && key(A[i]) != f(key(A[i]), key(A[L(i)]))) ok = false, left = key(A[L(i)]);
if (R(i) < N && key(A[i]) != f(key(A[i]), key(A[R(i)]))) ok = false, right = key(A[R(i)]);
if (!ok) {
let j = left == f(left, right) ? L(i) : R(i);
[A[i], A[j]] = [A[j], A[i]];
i = j;
}
} while (!ok);
return top;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment