A jenky start to my visualzing how an array can be made into a heap then a max-heap.
<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" href="./style.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.7.4/d3.js"></script>
</head>
<body>
<div id="heap">
</div>
<script src="heaper.js"></script>
</body>
</html>
var numbs = [ 1, 4, 7, 8, 2, 3, 1, 23, 21, 11, 67, 92, 29, 232, 9, 23, 87, 29, 8, 8, 6, 200]
var swapDelay = 1500;
var textTransDuration = 1500;
var margin = {top: 20, right: 90, bottom: 30, left: 90},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
var tau = 2 * Math.PI; // http://tauday.com/tau-manifesto
// An arc function with all values bound except the endAngle. So, to compute an
// SVG path string for a given angle, we pass an object with an endAngle
// property to the `arc` function, and it will return the corresponding string.
var arc = d3.arc()
.innerRadius(180)
.outerRadius(240)
.startAngle(0);
var i = 0,
duration = 750,
root;
var counter = 0;
var treeData = {};
var svg = d3.select("#heap")
.append("svg")
.attr("width", width + margin.right + margin.left)
.attr("height", height + margin.top + margin.bottom)
var g = svg.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
var tree = d3.tree()
.size([width, height]);
function buildHeap(inData){
var newsource = {name: inData[0], children: getChildren(0, inData) }
// console.log('dl', newsource)
root = d3.hierarchy(newsource, function(d) { return d.children; });
root.x0 = 0;
root.y0 = width/2;
update(root)
buildMaxHeap();
}
function buildMaxHeap(){
noders = d3.selectAll('g.node')
var numnodes = noders._groups[0].length;
var holders = {restartIndex: Math.floor((numnodes)/2)-1, bigChild:null}
max_heapify( Math.floor((numnodes)/2)-1, holders)
}
var noders
function max_heapify (ind, holders ){
console.log('max heap from ', nodes[ind])
noders = d3.selectAll('g.node')
holders.bigChild = bigChildIndex( ind )
holders.starter = ind;
var childindexes = []
childindexes = nodes[ind].children.map(function(d,i){
return d.id -1;
})
// console.log('childindexes are', childindexes)
var anode = d3.select('#nodey' + ind)
//console.log('anoder', anode)
var cirnode = anode.select('circle')
.transition()
.duration(duration+2000)
.style('fill', 'red')
.on('end', function(d) {
console.log('holders', holders)
compareChils(childindexes, holders)
})
var comptext = 'compare the childrens'
anode.append('text')
.text(comptext)
.attr("text-anchor", function(d) {
return 'middle'; })
.attr("dy", '20px')
.attr('class', 'process')
// console.log('anode: ', noders.select("#nodey"+ ind))
// var childers = noders.select('#nodey')
}
function compareChils( childsArr, holders){
console.log('goota compare and annimate, ', childsArr);
colorForComp(childsArr[0], holders);
colorForComp(childsArr[1], holders);
}
function colorForComp( inex, holders ) {
d3.select('#nodey' + inex)
.select('circle')
.transition()
.duration(duration+2000).style('fill', 'orange')
.on('end', function(d){
console.log('done and have ', d)
console.log('leaveing this orange this = ', this)
// console.log(nodes[holders.restartIndex].children[holders.bigChild])
if(nodes[holders.starter].children[holders.bigChild] === d){
console.log('its the big child need to check swaping')
d3.select(this).transition()
.duration(duration+200)
.style('fill','yellow')
.on('end', function(){
checkParentSwap(d, holders);
})
}
else{
console.log('this should make it green')
d3.select(this)
.transition()
.duration(duration+3000)
.style('fill','green')
}
})
}
function checkParentSwap(d, holders) {
// check if the given thing is bigger than the parent node
// and if not decrement holders.restartIndex and call the max heap thing with that
//console.log("d = " , d)
var childer = d;
var cnode = d3.select('#nodey' + (d.id-1));
var pnode = d3.select('#nodey' + (d.parent.id - 1));
d3.select('.process').text('Compare with largest child')
if(d.data.name > d.parent.data.name){
d3.select('.process').text('Compare with largest child')
.transition()
.duration(duration*10)
.delay(2000)
.text("swap with big child")
.on('end', function(d){
// console.log('swap with parent ', childer, holders);
swapWithParent(childer, holders)
})
.remove();
}
else{
cnode.select('circle')
.transition()
.duration(5000)
.style("fill", 'green')
d3.select('.process').text('This node is good move on')
.transition()
.duration(3000)
.delay(2000)
.remove();
if(holders.restartIndex > 0){
// console.log('need to color stuff here', pnode)
pnode.select('circle')
.transition()
.duration(3000)
.style("fill", 'green')
// console.log('we get to recur!!!')
holders.restartIndex = holders.restartIndex - 1;
max_heapify(holders.restartIndex, holders)
}
else{
colorAllCircsGreen();
console.log('its all over')
}
}
// blah blah
}
function colorAllCircsGreen() {
d3.selectAll('circle')
.transition()
.duration(2000)
.style('fill', 'green')
}
function swapWithParent(bigchild, holders){
var newLowval = bigchild.parent.data.name;
bigchild.parent.data.name = bigchild.data.name;
bigchild.data.name = newLowval;
var parnode = d3.select('#nodey' + (bigchild.parent.id -1) )
parnode
.select('circle')
.transition()
.duration(duration+5000)
.style('fill','green')
.on('end', function(){
parnode.select('.process')
.transition().delay(2000)
.remove();
})
var partext = parnode.select('.valtext');
console.log(partext)
partext
.transition()
.duration(textTransDuration)
.attr('transform', function(d){
return "translate(" + ( d.children[holders.bigChild].x -d.x) + ', ' + (d.children[holders.bigChild].y - d.y )+ ')'
})
.on('end', function(d){
d3.select(this).attr('transform', function(d){
console.log('trying to put it back', this, d)
return 'translate(0,0)'
})
.text('')
})
/*
.attr("x", function(d){
console.log('annimating parent text supposedly', d)
console.log(holders)
return d.x - d.children[holders.bigChild].x;
})
.attr("dy", function(d){
return (d.y - d.children[holders.bigChild].y )+ 'em';
});
*/
var chinode = d3.select('#nodey' + (bigchild.id - 1));
var chitext = chinode.select('.valtext');
chitext.transition()
.duration(textTransDuration)
.attr('transform', function(d){
//console.log('its this.x =', d3.select(this).attr('x'))
return "translate(" + (d.parent.x - d.x- d3.select(this).attr('x')) + ', ' + (d.parent.y - d.y )+ ')'
})
.on('end', function(d){
d3.select(this).attr('transform', function(d){
console.log('trying to put it back', this, d)
return 'translate(0,0)'
})
.text('')
})
chinode.select('circle').transition()
.duration(duration+2000)
.style('fill','red')
.on('end', function(d){
console.log('need to do stuff with ', d)
chinode.append('text')
.attr('class', 'process')
.text(function(d){
console.log(d)
console.log('and the holders', holders)
if(d.children){
console.log('need to keep ballancing')
if(d.children.length >0){
console.log('trying to maxheap with ', holders, d)
max_heapify(parseInt(d.id)-1, holders)
}
else{
console.log('in the wierd stpot moving on with the', holders)
console.log('make all circs white fill still')
chinode.select('circle').transition()
.duration(duration+2000)
.style('fill','green')
holders.restartIndex = holders.restartIndex - 1;
max_heapify(holders.restartIndex, holders)
}
}
else{
console.log('move on with the', holders)
console.log('make all circs white fill still')
chinode.select('circle').transition()
.duration(duration+2000)
.style('fill','green')
if(holders.restartIndex > 0){
holders.restartIndex = holders.restartIndex - 1;
max_heapify(holders.restartIndex, holders)
}
else{
console.log('done with it all')
colorAllCircsGreen();
}
}
return "Check for children";
})
.attr("text-anchor", function(d) {
return 'middle'; })
.attr("dy", '-20px')
.transition()
.duration(3000)
.delay(1000)
.style('fill', 'green')
.remove();
})
parnode.select('.process').remove();
upDateNodeVals()
}
function upDateNodeVals() {
d3.selectAll('g.node')
.transition()
.delay(swapDelay)
.select('text')
.text(function(d){
// console.log('need to change all the texts', d)
return d.data.name
})
}
function bigChildIndex(ind) {
console.log(ind);
var chillies = [];
if( nodes[ind] ){
chillies = nodes[ind].children;
if(chillies[1]){
return ( parseInt(chillies[0].data.name) > parseInt(chillies[1].data.name) ) ? 0 : 1;
}
else{
return 0;
}
}
else{
return -1;
}
// console.log(chillies)
}
// just leaving this global so i can mess with it in the console
var nodes;
function update(source){
var treeData = tree(root)
nodes = treeData.descendants();
var links = treeData.descendants().slice(1);
// ****************** Nodes section ***************************
// Update the nodes...
var node = g.selectAll('g.node')
.data(nodes, function(d) {return d.id || (d.id = ++i); });
// Enter any new modes at the parent's previous position.
var nodeEnter = node.enter().append('g')
.attr('class', 'node')
.attr("transform", function(d) {
return "translate(" + source.x0 + "," + source.y0 + ")";
})
.attr('id', function(d,i){
//console.log(d);
return "nodey" + i;
})
.on('click', click);
// Add Circle for the nodes
nodeEnter.append('circle')
.attr('class', 'node')
.attr('r', 1e-6)
.style("fill", function(d) {
return d._children ? "lightsteelblue" : "#fff";
});
// Add labels for the nodes
nodeEnter.append('text')
.attr("dy", ".35em")
.attr("x", function(d) {
return d.children || d._children ? -13 : 13;
})
.attr("text-anchor", function(d) {
return d.children || d._children ? "end" : "start";
})
.attr("class", "valtext")
.text(function(d) { return d.data.name; });
// UPDATE
var nodeUpdate = nodeEnter.merge(node);
// Transition to the proper position for the node
nodeUpdate.transition()
.duration(duration)
.attr("transform", function(d) {
return "translate(" + d.x + "," + d.y + ")";
});
// Update the node attributes and style
nodeUpdate.select('circle.node')
.attr('r', 10)
.style("fill", function(d) {
return d._children ? "lightsteelblue" : "#fff";
})
.attr('cursor', 'pointer');
// Remove any exiting nodes
var nodeExit = node.exit().transition()
.duration(duration)
.attr("transform", function(d) {
return "translate(" + source.x + "," + source.y + ")";
})
.remove();
// On exit reduce the node circles size to 0
nodeExit.select('circle')
.attr('r', 1e-6);
// On exit reduce the opacity of text labels
nodeExit.select('text')
.style('fill-opacity', 1e-6);
// ****************** links section ***************************
// Update the links...
var link = g.selectAll('path.link')
.data(links, function(d) { return d.id; });
// Enter any new links at the parent's previous position.
var linkEnter = link.enter().insert('path', "g")
.on('click', click)
.attr("class", "link")
.attr('d', function(d){
var o = {y: source.y0, x: source.x0}
return diagonal(o, o)
});
// UPDATE
var linkUpdate = linkEnter.merge(link);
// Transition back to the parent element position
linkUpdate.transition()
.duration(duration)
.attr('d', function(d){ return diagonal(d, d.parent) });
// Remove any exiting links
var linkExit = link.exit().transition()
.duration(duration)
.attr('d', function(d) {
var o = {x: source.x, y: source.y}
return diagonal(o, o)
})
.remove();
// Store the old positions for transition.
nodes.forEach(function(d, i){
// console.log(d)
d.x0 = d.x;
d.y0 = d.y;
});
nodes[0].name = 49
console.log(nodes)
//nodes[0].data.children = nodes[0].data._children;
//nodes[0].data._children = null;
//nodes
}
// Takes an index and an array and finds all the children.
// returns an array which can be added to children of the root node to
// make a json thing which can be used to make a d3.hierarchy();
function getChildren(i, arr) {
var childs = [];
if( arr[i+1+ i] ){
childs[0] = {name: arr[i*2+1], children: []}
if( arr[i+i+2] ){
// console.log(arr[i+1+ i], arr[i+i+2])
childs[1] = {name: arr[i * 2 + 2], children:[]} ;
}
}
var nextin = i * 2 + 1;
if(arr[nextin*2+1]){
// console.log('more children')
childs[0].children = getChildren(nextin, arr)
childs[0]._children = null;
if( arr[nextin*2 + 2 ]){
childs[1].children = getChildren(nextin+1, arr);
childs[1]._children = null;
}
}
return childs;
}
// Creates a curved (diagonal) path from parent to the child nodes
// switched around all the x's and y's from orig so it's verticle
function diagonal(s, d) {
//console.log('in diag and s = ', s);
//console.log('d = ', d)
path = `M ${s.x} ${s.y}
C ${(s.x + d.x) / 2} ${s.y},
${(s.x + d.x) / 2} ${d.y},
${d.x} ${d.y}`
return path;
}
// Toggle children on click.
function click(d) {
// use the following to superficially change the text of the node.
// this.getElementsByTagName('text')[0].textContent = "clicked all over"
console.log('clicked on: ', d)
}
buildHeap( numbs )
.node {
cursor: pointer;
}
.node circle {
fill: #fff;
stroke: steelblue;
stroke-width: 1.5px;
}
.node text {
font: 10px sans-serif;
}
.link {
fill: none;
stroke: #ccc;
stroke-width: 1.5px;
}