Mathematics undergraduate student at UFRJ
class FibonacciNode {
constructor(value) {
this.value = value;
this.parent = this.child = this.left = this.right = null;
this.degree = 0;
this.mark = false;
}
}
class FibonacciHeap {
constructor() {
// Pointer to the head and minimum node in the root list
this.root_list = null;
this.min_node = null;
// Maintain total node count in full fibonacci heap
this.total_nodes = 0;
}
// Merge a node with the doubly linked root_list
merge_with_root_list(node) {
if (this.root_list == null)
this.root_list = node;
else {
node.right = this.root_list.right;
node.left = this.root_list;
if (this.root_list.right != null)
this.root_list.right.left = node;
this.root_list.right = node;
}
}
// Insert new node into the unordered root list in O(1) time
insert(value) {
let n = new FibonacciNode(value);
n.left = n.right = n;
this.merge_with_root_list(n);
if (this.min_node == null || n.value < this.min_node.value)
this.min_node = n;
this.total_nodes++;
}
// Return min node in O(1) time
find_min() {
return this.min_node;
}
// Function to iterate through a doubly linked list
*iterate(head) {
let node = head;
let stop = head;
let flag = false;
while (true) {
if (node == stop && flag == true)
break;
if (node == stop)
flag = true;
yield node;
node = node.right;
}
}
// Make an array with all elements of the doubly linked list of the node passed
make_array(node) {
let A = [];
let iterator = this.iterate(node);
let curr = iterator.next();
while (curr.done === false) {
A.push(curr.value);
curr = iterator.next();
}
return A;
}
// Remove a node from the doubly linked root list
remove_from_root_list(node) {
if (node == this.root_list)
this.root_list = node.right;
node.left.right = node.right;
node.right.left = node.left;
}
// Merge a node with the doubly linked child list of a root node
merge_with_child_list(parent, node) {
if (parent.child == null)
parent.child = node;
else {
node.right = parent.child.right;
node.left = parent.child;
parent.child.right.left = node;
parent.child.right = node;
}
}
// Linking one node to another in the root_list while also updating the
// child linked list (linking y to x)
heap_link(y, x) {
this.remove_from_root_list(y);
y.left = y.right = y;
this.merge_with_child_list(x, y);
x.degree++;
y.parent = x;
}
// Combine root nodes of equal degree to consolidate the heap by creating a list of
// unordered binomial trees
consolidate() {
// Create an array of null elements with length total_nodes
let A = [];
for(let i=0; i < this.total_nodes; i++)
A.push(null);
// Put all nodes linked in root_list to an array
let nodes = this.make_array(this.root_list);
// For each node, check if there is another node with the same degree, and if so,
// link them together
for(let i=0; i < nodes.length; i++) {
let x = nodes[i];
let d = x.degree;
while (A[d] != null) {
let y = A[d];
// We will link y to x, with x being the parent and y the child.
// So if the value of x is greater than y, we swap them.
if (x.value > y.value) {
let temp = x;
x = y;
y = temp;
}
this.heap_link(y, x);
A[d] = null;
d++;
}
A[d] = x;
}
// Find new min node - no need to reconstruct new root list below because root list
// was iteratively changing as we were moving nodes around in the above loop
for(let i=0; i < A.length; i++) {
if (A[i] != null) {
if (A[i].value < this.min_node.value) {
this.min_node = A[i];
}
}
}
}
// Extract (delete) the min node from the heap in O(log n) time
// amortized cost
extract_min() {
let min = this.min_node;
if (min != null) {
if (min.child != null) {
// Create an array with all the children of min
let children = this.make_array(min.child);
// Attach child nodes to root_list
for(let i=0; i < children.length; i++) {
this.merge_with_root_list(children[i]);
children[i].parent = null;
}
}
this.remove_from_root_list(min);
// Set new min node in heap:
//
// When min is the only node in root_list
if (min == min.right)
this.min_node = this.root_list = null;
else {
this.min_node = min.right;
this.consolidate();
}
this.total_nodes--;
}
return min;
}
// Remove a node from the doubly linked child list
remove_from_child_list(parent, node) {
// If there is only one node in the child list we just set
// parent.child to null
if (parent.child == parent.child.right)
parent.child = null;
if (parent.child == node) {
parent.child = node.right;
node.right.parent = parent;
}
else {
node.left.right = node.right;
node.right.left = node.left;
}
}
// If a child node becomes smaller than its parent node we cut this child node off and
// bring it up to the root list
cut(node, parent) {
this.remove_from_child_list(parent, node);
parent.degree--;
this.merge_with_root_list(node);
node.parent = null;
node.mark = false;
}
// Cascading cut of parent node
cascading_cut(node) {
let parent = node.parent;
if (parent != null) {
if (node.mark == false)
node.mark = true;
else {
this.cut(node, parent);
this.cascading_cut(parent);
}
}
}
// Modify the value of some node in the heap in O(1) time
decrease_key(node, new_value) {
if (new_value > node.value)
return null;
node.value = new_value;
let parent = node.parent;
if (parent != null && node.value < parent.value) {
this.cut(node, parent);
this.cascading_cut(parent);
}
if (node.value < this.min_node.value)
this.min_node = node;
}
// Delete a node from the structure
delete_node(node) {
let parent = node.parent;
let child = node.child;
let A = []; // Array that will contain all nodes that will be merged to the root_list
// If the node has children, we add them to array A
if (child != null)
A = this.make_array(child);
// Base case, when it is a root node
if (parent == null)
this.remove_from_root_list(node);
if (parent != null) {
this.remove_from_child_list(parent, node);
parent.degree--;
// Checking if parent is set to false and if it is not a root node, so we can set
// parent.mark to true
if (parent.mark == false && parent.parent != null)
parent.mark = true;
}
// If parent.mark is set to true, we need to perform a cascating cut
while (parent.mark === true) {
A.push(parent);
this.remove_from_child_list(parent.parent, parent);
parent = parent.parent;
}
// Merging nodes from A to root_list
for(let i=0; i < A.length; i++) {
this.merge_with_root_list(A[i]);
A[i].parent = null;
A[i].mark = false;
}
}
// Merge two fibonacci heaps in O(1) time by concatenating the root lists. The root of the new
// root list becomes equal to the first list and the second list is simply appended to the end
// (then the proper min node is determined)
merge(h2) {
// Creating a copy of the original heap
let h1 = new FibonacciHeap();
h1.root_list = this.root_list;
h1.min_node = this.min_node;
// Fix pointers when merging the two heaps
let last = h2.root_list.left;
// Linking the first root node of h2 to the last of h1
h2.root_list.left = h1.root_list.left;
h1.root_list.left.right = h2.root_list;
// Linking the firt node of h1 to the last of h2
h1.root_list.left = last;
h1.root_list.left.right = h1.root_list
// Update min node if needed
if (h2.min_node < h1.min_node)
h1.min_node = h2.min_node;
// Update total nodes
h1.total_nodes = this.total_nodes + h2.total_nodes;
return h1;
}
}
t1 = {
let t = new FibonacciHeap();
for(let i=0; i<4; i++) {
t.insert(i);
}
t.consolidate();
// t.delete_node(t.root_list.child.right);
let min = t.extract_min();
return t;
}
t2 = {
let t = new FibonacciHeap();
for(let i=4; i<9; i++) {
t.insert(i);
}
t.consolidate();
// t.remove_from_root_list(t.root_list);
return t;
}
// Testing t.merge() with t1 abd t2
t3 = {
let t1 = new FibonacciHeap();
for(let i=0; i<4; i++) {
t1.insert(i);
}
t1.consolidate();
let t2 = new FibonacciHeap();
for(let i=4; i<9; i++) {
t2.insert(i);
}
t2.consolidate();
let t3 = t1.merge(t2);
return t3;
}
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.
