Skip to content

Instantly share code, notes, and snippets.

@yusufnb

yusufnb/heap.html

Created April 14, 2014 05:40
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save yusufnb/10619063 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save yusufnb/10619063 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. yusufnb created this gist Apr 14, 2014.
    88 changes: 88 additions & 0 deletions heap.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,88 @@
    <script>
    var Heap = (function(){
    'use strict';
    var arr = [];
    function parent(i) {
    return Math.floor((i+1)/2) - 1;
    }
    function left(i) {
    return (i+1)*2 - 1;
    }
    function right(i) {
    return (i+1)*2;
    }
    function swap(i, j) {
    var t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    }
    var self = {
    add: function(n) {
    var i = arr.length;
    arr[i] = n;
    while(i > 0) {
    if (arr[parent(i)] < arr[i]) {
    swap(parent(i), i);
    i = parent(i);
    } else {
    break;
    }
    }
    return arr;
    },
    remove: function() {
    var size = arr.length;
    var max = arr[0];
    arr[0] = arr[arr.length - 1];
    arr.splice(arr.length - 1, 1);
    var i = 0;
    while (i < arr.length - 1) {
    if (left(i) >= arr.length && right(i) < arr.length && arr[i] < arr[right(i)]) {
    swap(i, right(i));
    i = right(i);
    continue;
    }
    if (right(i) >= arr.length && left(i) < arr.length && arr[i] < arr[left(i)] ) {
    swap(i, left(i));
    i = left(i);
    continue;
    }
    if (left(i) < arr.length && right(i) < arr.length) {
    // Non left
    if (arr[i] < arr[left(i)] || arr[i] < arr[right(i)]) {
    if (arr[right(i)] < arr[left(i)]) {
    swap(i, left(i));
    i = left(i);
    continue;
    } else {
    swap(i, right(i));
    i = right(i);
    continue;
    }
    } else {
    break;
    }
    }
    break;
    }
    return max;
    },
    set: function(a) {
    arr = a;
    }

    };

    return self;
    })();

    console.log(Heap.add(1), 'Heap.add(1)');
    console.log(Heap.add(2), 'Heap.add(2)');
    console.log(Heap.add(3), 'Heap.add(3)');
    console.log(Heap.add(4), 'Heap.add(4)');
    console.log(Heap.remove(), 'Heap.remove()');

    </script>
    <body>
    See console logs
    </body>