animation of balancing a heap into a max-heap

readme.md

A jenky start to my visualzing how an array can be made into a heap then a max-heap.

heaper.js

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 )

index.html

<!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>

style.css

.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;
}

thumbnail.png