While researching binary tree implementations in JavaScript, I ran across Marijn Haverbeke's implementation from the first edition of Eloquent JavaScript. What I especially like about this implementation is the use of sequential representation of a binary tree.

I re-factored (using newer syntax, as the first edition is pre-ES6) and annotated:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
function BinaryHeap(compare) {
this.content = [];
this.compare = compare;
}

BinaryHeap.prototype = {
push: function(element) {
this.content.push(element);
this.bubbleUp(this.content.length - 1);
},

pop: function() {
// Remove the first element from the tree,
// and store it to remove it.
let result = this.content.shift();

// When removing an element from a minHeap,
// we remove the last element, place it at
// the top, then allow it to sink down the
// tree.
if (this.content.length) {
this.content.unshift(this.content.pop());
this.sinkDown(0);
}

return result;
},

peek: function() {
return this.content[0];
},

size: function() {
return this.content.length;
},

bubbleUp: function(index) {
// We now iterate through the tree, which is represented here as an array.
// (See: https://www.geeksforgeeks.org/binary-tree-array-implementation/)
//
// To do so with a zero-indexed tree, which looks like this:
//
//. A(0)
//. / \
//. B(1) C(2)
//. / \ \
//. D(3) E(4) F(5)
//
// Then, with parent P, then the left child is (2*P)+1, and the right
// child is (2*P)+2;
//
// Thus, the left child of B is:
//
// (2 * 1) + 1 = 3.
//
// While the right child is:
//
// (2 * 1)+ 2 = 4.

while (index > 0) {
let valueToInsert = this.content[index];

// To calculate the parent of a node, say the parent of node E
// in the example above, we can do the following calculation:
//
// Math.floor((E + 1) / 2) - 1 =
// Math.floor(5 / 2) - 1 =
// 2 - 1 = 1
//
// Similarly, to calculate the parent of F, we do the following:
//
// Math.floor((F + 1) / 2) - 1 =
// 3 - 1 = 2

let parentNodeIndex = Math.floor((index + 1) / 2) - 1;

if (this.compare(
this.content[parentNodeIndex],
this.content[index])) {

// If the child node's value is (for a minHeap) greater than the parent node,
// we're done, e.g. the parent node value must be less than
break;

} else {
// Otherwise, we're going to need to swap the two values.
// this.swap(this.content[index], this.content[parentNodeIndex])
let tmp = this.content[parentNodeIndex];
this.content[parentNodeIndex] = valueToInsert;
this.content[index] = tmp;

// We're simply climbing up the binary tree
// here, comparing each node with its parent.
index = parentNodeIndex;
}
}
},

sinkDown: function(index) {
let length = this.content.length;

// we'll need to sink down the value at the index
// the function is given.
let valueToInsert = this.content[index];

// We now traverse the tree downwards.
while (true) {
let rightChildIndex = (index + 1) * 2;
let leftChildIndex = rightChildIndex - 1;
let swapIndex = null;

// see if the left child exists.
if (leftChildIndex < length) {
// If so, if the left child's value is (for a minHeap)
// less than the index's value, prepare to swap the two.
if (this.compare(
this.content[leftChildIndex],
this.content[index]))
swapIndex = leftChildIndex;
}

// see if the right child exists.
if (rightChildIndex < length) {
// If the right element is (for a minHeap) lower than the left element (and
// as a function of the logic, lower than the parent index) then swap with the parent
// index.
if (this.compare(this.content[rightChildIndex],
(swapIndex === null ? this.content[index] : this.content[leftChildIndex]))) {
swapIndex = rightChildIndex;
}
}

// if there's nothing to swap, break.
if (swapIndex === null) break;

// The value with either the parent, or other child.
this.content[index] = this.content[swapIndex];
this.content[swapIndex] = valueToInsert;

// Now, do the same process on the same value, but in the position of the
// node with which we swapped.
index = swapIndex;
}
}
}

var minHeap = new BinaryHeap((a, b) => a <= b);
([10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 5].forEach((x) => minHeap.push(x)));
while (minHeap.content.length) console.log(minHeap.pop());

var maxHeap = new BinaryHeap((a, b) => a >= b);
([10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 5].forEach((x) => maxHeap.push(x)));
while (maxHeap.content.length) console.log(maxHeap.pop());