Public
Edited
Dec 13, 2022
// Heap property is minimum
// all(Node <= child for child in children)
class BHeap {
constructor(weightfunc) {
this.weightfunc = weightfunc;
this.arr = []; // Internal tree storage
this.dbg = "";
}
debug(s) {
this.dbg = `${this.dbg}${s}\n`;
}
getDbg() { return this.dbg; }
parentI(i) {
return Math.floor((i-1)/2);
}
lchildI(i) {
return (2*i)+1;
}
rchildI(i) {
return (2*i)+2;
}
add(item) {
if (this.weightfunc) {
let weight = this.weightfunc(item);
let obj = {
item,
weight
};
this.arr.push(obj);
this.percUp(this.arr.length-1, obj);
} else {
this.arr.push(item);
this.percUp(this.arr.length-1, item);
}
}
addAll(...items) {
for (let i of items) {
if (i.length != undefined) {
for (let it of i) {
this.add(it);
}
} else {
this.add(i);
}
}
}
lt(a, b) {
if (this.weightfunc)
return a.weight < b.weight
else return a < b;
}
popMin() {
let min = this.arr[0];
if (this.arr.length > 1) {
// Remove the last leaf node and percolate it
this.percDown(0, this.arr.pop());
} else {
this.arr.pop()
}
return this.weightfunc ? min.item : min;
}
// "Heapify" (percolate/bubble down)
percDown(i, value) {
let N = this.arr.length;
if (this.lchildI(i) >= N) {
// Leaf node: done!
this.arr[i] = value;
} else if (this.lchildI(i) == (N-1)) {
// Left node is last:
if (this.lt(this.arr[this.lchildI(i)], value)) {
// Swap
this.arr[i] = this.arr[this.lchildI(i)];
this.arr[this.lchildI(i)] = value;
} else {
// All is good
this.arr[i] = value;
}
} else {
let j = 0;
// is left child < right child?
if (this.lt(this.arr[this.lchildI(i)], this.arr[this.rchildI(i)]))
j = this.lchildI(i);
else
j = this.rchildI(i);
// Need to heapify some more?
if (this.lt(this.arr[j], value)) {
this.arr[i] = this.arr[j];
this.percDown(j, value);
} else {
this.arr[i] = value;
}
}
}
percUp(i, value) {
if (i == 0) {
this.arr[i] = value;
} else if (this.lt(this.arr[this.parentI(i)], value)) {
this.arr[i] = value;
} else {
this.arr[i] = this.arr[this.parentI(i)];
this.percUp(this.parentI(i), value);
}
}
peekMin() {
return this.weightfunc ? this.arr[0].item : this.arr[0];
}
getRaw() {
return this.arr
}
get length() {
return this.arr.length;
}
}
test1 = {
let items = [1,23,12,5,25,634,21,4,5,23,6,2,0]
let heap = new BHeap();
heap.addAll(items)
let out = []
while (heap.length)
out.push(heap.popMin());
return {
out,
debug: heap.getDbg(),
}["out"]
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
