-
-
Save stev47/3181499 to your computer and use it in GitHub Desktop.
Building a heap from array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta http-equiv="Content-Type" content="text/html;charset=utf-8"> | |
| <script type="text/javascript" src="http://d3js.org/d3.v2.js"></script> | |
| <script type="text/javascript" src="mootools-core.js"></script> | |
| <script type="text/javascript" src="mootools-more.js"></script> | |
| <script type="text/javascript" src="heap.js"></script> | |
| <style> | |
| .link { | |
| fill: none; | |
| stroke: #999; | |
| stroke-width: 2px; | |
| } | |
| .node ellipse { | |
| fill: #FFF; | |
| stroke: #000; | |
| stroke-width: 1px; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div id="viz"></div> | |
| <script type="text/javascript"> | |
| function create_sample (n) { | |
| var array = []; | |
| for (var i = 0; i < n; i++) | |
| array[i] = i; | |
| for (var i = 0; i < n; i++) { | |
| var j = Math.floor(Math.random()*n); | |
| var tmp = array[i]; | |
| array[i] = array[j]; | |
| array[j] = tmp; | |
| } | |
| return array; | |
| } | |
| // "vis" actually holds the svg-group element | |
| var vis = d3.select("#viz").append("svg") | |
| .attr("width", 940) | |
| .attr("height", 400) | |
| .append("g") | |
| .attr("transform", "translate(0, 40)"); | |
| var tree = d3.layout.tree() | |
| .size([940, 300]); | |
| var diagonal = d3.svg.diagonal(); | |
| function update (tree_data) { | |
| var tree = d3.layout.tree().size([940,300]) | |
| tree.separation(function (a, b) { | |
| return (a.parent == b.parent)? 10 : 12; | |
| }); | |
| var nodes = tree.nodes(tree_data); | |
| var link = vis.selectAll("path.link") // "path.link" is a css selector (doesn't matter here) | |
| .data(tree.links(nodes)) | |
| .enter().append("path") | |
| .attr("class", "link") | |
| .attr("d", diagonal); | |
| var node = vis.selectAll("g.node") | |
| .data(nodes, function (d) { | |
| return d.value; | |
| }); | |
| node.select("ellipse").transition().style("fill", function (d) { | |
| if (d.status == "heapify") | |
| return "#F99"; | |
| if (d.status == "compare") | |
| return "#FF9"; | |
| return "#FFF"; | |
| }) | |
| node.transition().delay(100) | |
| .attr("transform", function (d) { | |
| return "translate(" + d.x + "," + d.y + ")"; | |
| }) | |
| var new_node = node.enter() | |
| .append("g") | |
| .attr("class", "node") | |
| .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); | |
| new_node.append("ellipse") | |
| .attr("rx", 17) | |
| .attr("ry", function(d) { | |
| return 30 / d.depth; | |
| }) | |
| new_node.append("text") | |
| .attr("dy", "0.5ex") | |
| .attr("text-anchor", "middle") | |
| .text(function(d) { return d.value; }); | |
| node.exit() | |
| .remove(); | |
| } | |
| var my_heap = new Heap(create_sample(50), 2); | |
| function heap_state_update () { | |
| if (my_heap.states.length <= 0) { | |
| return; | |
| } else { | |
| update(my_heap.states.shift()); | |
| setTimeout(heap_state_update, 500); | |
| } | |
| } | |
| heap_state_update(); | |
| </script> | |
| </body> | |
| </html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| A heap is represented as an object. | |
| Each node has an attribute "value" containing the node value | |
| and an attribute "children" containing an array of child nodes (if any) | |
| */ | |
| var Heap = new Class ({ | |
| states: [], | |
| heap: [], | |
| initialize: function(values, num_children) { | |
| // number of tree nodes | |
| this.n = values.length; | |
| for (var i = 0; i < this.n; i++) { | |
| this.heap.push({ | |
| value : values[i] | |
| }); | |
| } | |
| // number of children for each node | |
| this.m = num_children; | |
| // push initial state | |
| this.states.push(this.getTree()); | |
| for (var node = this.n - 1; node >= 0; node--) { | |
| this.heapify(node); | |
| } | |
| this.states.push(this.getTree()); | |
| }, | |
| swap: function (a, b) { | |
| var tmp = this.heap[a].value; | |
| this.heap[a].value = this.heap[b].value; | |
| this.heap[b].value = tmp; | |
| }, | |
| heapify: function (node) { | |
| if (this.m * node + 1 > Math.min(this.n - 1, this.m * (node + 1))) | |
| return false; | |
| this.heap[node].status = "heapify"; | |
| var min = node; | |
| for (var child = this.m * node + 1; child <= Math.min(this.n - 1, this.m * (node + 1)); child++) { | |
| this.heap[child].status = "compare"; | |
| if (this.heap[child].value < this.heap[min].value) | |
| min = child; | |
| } | |
| this.states.push(this.getTree()); | |
| for (var child = this.m * node + 1; child <= Math.min(this.n - 1, this.m * (node + 1)); child++) { | |
| this.heap[child].status = ""; | |
| } | |
| if (min != node) { | |
| this.swap(node, min); | |
| // push current state; | |
| this.states.push(this.getTree()); | |
| this.heapify(min); | |
| this.heap[node].status = ""; | |
| return true; | |
| } else { | |
| this.heap[node].status = ""; | |
| return false; | |
| } | |
| }, | |
| getNodeTree: function (node) { | |
| var obj = Object.clone(this.heap[node]); | |
| obj.children = []; | |
| for (var child = this.m * node + 1; child <= Math.min(this.n - 1, this.m * (node + 1)); child++) { | |
| obj.children.push(this.getNodeTree(child)); | |
| } | |
| return obj; | |
| }, | |
| getTree: function () { | |
| return this.getNodeTree(0); | |
| } | |
| }) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta http-equiv="Content-Type" content="text/html;charset=utf-8"> | |
| <script type="text/javascript" src="http://d3js.org/d3.v2.js"></script> | |
| <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/mootools/1.4.5/mootools-yui-compressed.js"></script> | |
| <script type="text/javascript" src="heap.js"></script> | |
| <style> | |
| .link { | |
| fill: none; | |
| stroke: #999; | |
| stroke-width: 2px; | |
| } | |
| .node ellipse { | |
| fill: #FFF; | |
| stroke: #000; | |
| stroke-width: 1px; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div id="viz"></div> | |
| <script type="text/javascript"> | |
| function create_sample (n) { | |
| var array = []; | |
| for (var i = 0; i < n; i++) | |
| array[i] = i; | |
| for (var i = 0; i < n; i++) { | |
| var j = Math.floor(Math.random()*n); | |
| var tmp = array[i]; | |
| array[i] = array[j]; | |
| array[j] = tmp; | |
| } | |
| return array; | |
| } | |
| // "vis" actually holds the svg-group element | |
| var vis = d3.select("#viz").append("svg") | |
| .attr("width", 940) | |
| .attr("height", 400) | |
| .append("g") | |
| .attr("transform", "translate(0, 40)"); | |
| var tree = d3.layout.tree() | |
| .size([940, 300]); | |
| var diagonal = d3.svg.diagonal(); | |
| function update (tree_data) { | |
| var tree = d3.layout.tree().size([940,300]) | |
| tree.separation(function (a, b) { | |
| return (a.parent == b.parent)? 10 : 12; | |
| }); | |
| var nodes = tree.nodes(tree_data); | |
| var link = vis.selectAll("path.link") // "path.link" is a css selector (doesn't matter here) | |
| .data(tree.links(nodes)) | |
| .enter().append("path") | |
| .attr("class", "link") | |
| .attr("d", diagonal); | |
| var node = vis.selectAll("g.node") | |
| .data(nodes, function (d) { | |
| return d.value; | |
| }); | |
| node.select("ellipse").transition() | |
| .style("fill", function (d) { | |
| if (d.status == "heapify") | |
| return "#F99"; | |
| if (d.status == "compare") | |
| return "#FF9"; | |
| return "#FFF"; | |
| }) | |
| .attr("rx", function(d) { | |
| return 50 / Math.pow(d.depth + 1, 0.8); | |
| }); | |
| node.transition() | |
| .attr("transform", function (d) { | |
| return "translate(" + d.x + "," + d.y + ")"; | |
| }); | |
| var new_node = node.enter() | |
| .append("g") | |
| .attr("class", "node") | |
| .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); | |
| new_node.append("ellipse") | |
| .attr("ry", 13) | |
| .attr("rx", function(d) { | |
| return 50 / Math.pow(d.depth + 1, 0.8); | |
| }); | |
| new_node.append("text") | |
| .attr("dy", "0.5ex") | |
| .attr("text-anchor", "middle") | |
| .text(function(d) { return d.value; }); | |
| node.exit() | |
| .remove(); | |
| } | |
| var my_heap = new Heap(create_sample(50), 2); | |
| function heap_state_update () { | |
| if (my_heap.states.length <= 0) { | |
| return; | |
| } else { | |
| update(my_heap.states.shift()); | |
| setTimeout(heap_state_update, 500); | |
| } | |
| } | |
| heap_state_update(); | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment