30:T797,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 // 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; }31:[] 2e:{"title":"Binary Heaps","cells":[{"id":0,"value":"md`# Binary Heaps\n\nA simple implementation of a (Max) binary heap.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":72,"value":"md`## Insertion demo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"{\n let h = new Heap();\n let div = html`

`;\n for (let x of [1,2,3,4,8,5,6]) {\n h.insert(x)\n div.append(html`

${x} inserted${draw(h)}

`);\n }\n return div;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":69,"value":"md`## Deletion demo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"{\n let h = new Heap(1,2,3,4,8,5,6);\n let div = html`

${draw(h)}

`;\n while (h.length>0) {\n let x = h.top();\n h.delTop();\n div.append(html`

${x} deleted${draw(h)}

`);\n }\n return div;\n}\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":53,"value":"function draw(heap) {\n let result = `graph{ `;\n const str = (h) => (Array.isArray(h) ? `\"${h[0]}(${h.slice(1)})\"` : `\"${h}\"`);\n for (let i = 0; i < heap.length; i++) {\n let x = str(heap[i]);\n if (i == 0) result += `${x};`;\n else {\n let p = str(heap[~~((i - 1) / 2)]);\n result += `${p}--${x};`;\n }\n }\n result += \"}\";\n return dot`${result}`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":48,"value":"dot = require(\"@observablehq/graphviz@0.2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"import {graphViz,CompleteBinaryTree} from \"@esperanc/trees\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}