Public
Script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
export let heapify = (arr) => {
// maxHeap
const swapDown = (arr, n, i) => {
// Recursively swap entries if they are less than their children.
// The first index to be checked will be the last non-leaf (floor(n/2 - 1)),
// since we only really call this from insert and delete.
let largest = i; // assume the current index is the largest.
const left = 2 * i + 1; // because math (binary tree)
const right = 2 * i + 2; // because math
// Check if left child of current node is greater, satisfying the heap
// criterion. (We also need to be "in-bounds")
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// Check if the right child is greater than the left
// We need to know this because if we merely replaced the
// parent with the first large child, we might still violate
// the heap property in our new tree.
if (left < n && arr[right] > arr[largest]) {
largest = right;
}
// Now actually perform the swap.
// Note that we only need to do this if one of the children was larger
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
// We can assume we've already processed higher-up nodes,
// so we don't need to continue if the heap property is satisfied for
// this sub-tree.
swapDown(arr, n, largest);
}
};
// parseInt to round down
for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
swapDown(arr, arr.length, i);
}
return arr;
};
Val Town is a social website to write and deploy JavaScript.
Build APIs and schedule functions from your browser.
Comments
Nobody has commented on this val yet: be the first!
October 23, 2023