Published
Edited
Jul 25, 2022
1 star
push = () => {
// maintain a list of heaps (store a pointer to the root of each heap)
let rootlist = []
// maintain a pointer to the smallest root
let minroot = null;
function push(v, k) {
// create a new heap h consisting of a single item (v, k)
// add h to the list of roots like Linked List Priority Queue
// update minroot if k < minroot.key
}
}
function merge() {
/* To merge two binomial heaps, start from degree 0 and go up, as if doing binary addition,
but instead of adding digits in place k we merge binomial trees of degree k, keeping the
tree with smaller root on top */
}
function cleanup(roots) {
let root_array = new Array(roots.length);
roots.forEach((t) => {
let x = t;
while (root_array[x.degree] !== undefined) {
let u = root_array[x.degree];
root_array[x.degree] = undefined;
let x = merge(x, u);
root_array[x.degree] = x;
}
});
// retorna apenas os elementos diferentes de "undefined" organizados em ordem decrescente
return root_array.reverse().filter((t) => t !== undefined);
};
// every node will store a flag, p.loser = True / False
function decreasekey(v, k) {
// finds the node by value
let n = find(v);
n.key = k;
// if n is a root, update minroot if necessary
if (n.key < n.parent.key) { // if n violates the heap condition
let p = null;
while (p.loser === true || p === null) {
p = n.parent;
// remove n from p children
// insert n into rootlist, updating minroot if necessary
n.loser = false; // root can't be "loser"
n = p;
};
if (p.parent !== null) { // if p is not a root
p.loser = true;
};
};
}
function popmin() {
// marke all of minroot's children as "loser = false" because root can't be "loser"
// then do the same in other version
}
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.
