Computer Graphics & Visualization @ufrj.br
Point k-d trees with queriesHash table with open addressing and double hashingHash table with separate chainingPoint k-d treesOmohundro balltree construction algorithmsCounting and radix sortMergeSort and QuickSortSkipListSplay TreesTreaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
Binary Heaps
Heap = {
function left(i) {
return 2 * i + 1;
}
function right(i) {
return 2 * i + 2;
}
function parent(i) {
return ~~((i - 1) / 2);
}
function lessThan(a, b) {
return Array.isArray(a) ? a[0] < b[0] : a < b;
}
//
// A Max heap (top element is the maximum)
//
class Heap extends Array {
constructor(...args) {
super(...args);
for (let i = ~~(this.length / 2); i >= 0; i--) this.heapify(i);
}
// Makes sure that element i is bigger than either son.
// If no swap is needed, returns false, otherwise returns swaps the element with the biggest son
// and returns it index
heapify(i) {
let [l, r, max] = [left(i), right(i), i];
if (
l < this.length &&
lessThan(this[max], this[l]) /*this[l] > this[max]*/
)
max = l;
if (
r < this.length &&
lessThan(this[max], this[r]) /* this[r] > this[max]*/
)
max = r;
if (max != i) {
[this[i], this[max]] = [this[max], this[i]];
this.heapify(max);
return max;
}
return false;
}
// Fixes things towards the top if i is bigger than parent
bubbleup(i) {
if (i == 0) return;
let p = parent(i);
if (this.heapify(p)) this.bubbleup(p);
}
// Fixes things downwards if i is smaller than one of its sons
sinkdown(i) {
if (i >= this.length) return;
let j = this.heapify(i);
if (j) this.sinkdown(j);
}
// Inserts x into the heap
insert(x) {
this.push(x);
this.bubbleup(this.length - 1);
}
// Top of the heap (max value)
top() {
if (this.length == 0) throw "Empty Heap";
return this[0];
}
// Removes the top
delTop() {
if (this.length == 0) throw "Empty Heap";
let x = this.pop();
if (this.length == 0) return;
this[0] = x;
this.sinkdown(0);
}
}
return Heap;
}
{
let h = new Heap();
let div = html`<div></div>`;
for (let x of [1,2,3,4,8,5,6]) {
h.insert(x)
div.append(html`<div><span style='vertical-align:top'>${x} inserted</span>${draw(h)}</div>`);
}
return div;
}
{
let h = new Heap(1,2,3,4,8,5,6);
let div = html`<div>${draw(h)}</div>`;
while (h.length>0) {
let x = h.top();
h.delTop();
div.append(html`<div><span style='vertical-align:top'>${x} deleted</span>${draw(h)}</div>`);
}
return div;
}
function draw(heap) {
let result = `graph{ `;
const str = (h) => (Array.isArray(h) ? `"${h[0]}(${h.slice(1)})"` : `"${h}"`);
for (let i = 0; i < heap.length; i++) {
let x = str(heap[i]);
if (i == 0) result += `${x};`;
else {
let p = str(heap[~~((i - 1) / 2)]);
result += `${p}--${x};`;
}
}
result += "}";
return dot`${result}`;
}
dot = require("@observablehq/graphviz@0.2")
import {graphViz,CompleteBinaryTree} from "@esperanc/trees"
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.
