Public
Edited
Aug 26, 2024
4 stars
buildTree = count => {
const pq = new PriorityQueue({ priority: 'count' });
Object.entries(count).forEach(([k, v]) =>
pq.insert({
symb: k,
count: v
})
);
while (!pq.empty()) {
const a = pq.extract();
if (pq.empty()) return a;
const b = pq.extract();
a.digit = 0;
b.digit = 1;
const e = {
symb: null,
count: a.count + b.count,
children: [a, b]
};
pq.insert(e);
}
}
PriorityQueue = {
const INF = Number.POSITIVE_INFINITY;
const left = i => 2 * i + 1;
const right = i => 2 * i + 2;
const parent = i => (i > 0 ? Math.floor((i - 1) / 2) : null);
const Heap = class {
constructor(params = {}) {
const { args, priority } = params;
this.arr = [];
this.prop = priority;
this.counter = 0;
for (const e of args || []) this.insert(e);
}
empty() {
return this.arr.length === 0;
}
extract() {
if (!this.arr.length) return null;
const e = this.arr[0];
this.swap(0, this.arr.length - 1);
this.arr.pop();
this.moveDown(0);
return e;
}
insert(e) {
this.counter += 1;
this.arr.push(e);
this.moveUp(this.arr.length - 1);
}
moveUp(i) {
const p = parent(i);
if (this.arr[p] && this.arr[p][this.prop] > this.arr[i][this.prop]) {
this.swap(p, i);
this.moveUp(p);
} else {
}
}
moveDown(i) {
const cl = left(i);
const cr = right(i);
const cm = !this.arr[cl]
? null
: !this.arr[cr]
? cl
: this.arr[cl][this.prop] < this.arr[cr][this.prop]
? cl
: cr;
if (
cm &&
this.arr[cm] &&
this.arr[cm][this.prop] < this.arr[i][this.prop]
) {
this.swap(cm, i);
this.moveDown(cm);
}
}
swap(i, j) {
const temp = this.arr[i];
this.arr[i] = this.arr[j];
this.arr[j] = temp;
}
};
return Heap;
}
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.
