Skip to content

Instantly share code, notes, and snippets.

@nikolenkoanton92

nikolenkoanton92/Heap.js

Forked from linfongi/Heap.js
Created June 27, 2021 03:39
Show Gist options

  • Select an option

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

Select an option

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

Revisions

  1. @linfongi linfongi revised this gist Jun 8, 2018. 1 changed file with 5 additions and 1 deletion.
    6 changes: 5 additions & 1 deletion Heap.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,10 @@
    function Heap(compare = (a, b) => a - b) {
    const arr = [];
    return { push, pop, peek };
    return { push, pop, peek, size };

    function size() {
    return arr.length;
    }

    function push(v) {
    arr.push(v);
  2. @linfongi linfongi revised this gist May 1, 2018. 1 changed file with 5 additions and 6 deletions.
    11 changes: 5 additions & 6 deletions Heap.js
    View file
    Original file line number Diff line number Diff line change
    @@ -36,15 +36,14 @@ function Heap(compare = (a, b) => a - b) {
    let i = 0;
    for (;;) {
    let next = i;
    if (i * 2 < arr.length && compare(arr[i * 2], arr[next]) < 0) {
    next = i * 2;
    }
    if (i * 2 + 1 < arr.length && compare(arr[i * 2 + 1], arr[next]) < 0) {
    next = i * 2 + 1;
    for (const childIdx of [i * 2 + 1, i * 2 + 2]) {
    if (childIdx < arr.length && compare(arr[childIdx], arr[next]) < 0) {
    next = childIdx;
    }
    }
    if (next === i) return;
    [arr[i], arr[next]] = [arr[next], arr[i]];
    i = next;
    }
    }
    }
    }
  3. @linfongi linfongi revised this gist May 1, 2018. 1 changed file with 3 additions and 4 deletions.
    7 changes: 3 additions & 4 deletions Heap.js
    View file
    Original file line number Diff line number Diff line change
    @@ -36,15 +36,14 @@ function Heap(compare = (a, b) => a - b) {
    let i = 0;
    for (;;) {
    let next = i;
    if (i * 2 < arr.length && compare(arr[i * 2], arr[i]) < 0) {
    [arr[i * 2], arr[i]] = [arr[i], arr[i * 2]];
    if (i * 2 < arr.length && compare(arr[i * 2], arr[next]) < 0) {
    next = i * 2;
    }
    if (i * 2 + 1 < arr.length && compare(arr[i * 2 + 1], arr[i]) < 0) {
    [arr[i * 2 + 1], arr[i]] = [arr[i], arr[i * 2 + 1]];
    if (i * 2 + 1 < arr.length && compare(arr[i * 2 + 1], arr[next]) < 0) {
    next = i * 2 + 1;
    }
    if (next === i) return;
    [arr[i], arr[next]] = [arr[next], arr[i]];
    i = next;
    }
    }
  4. @linfongi linfongi revised this gist May 1, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Heap.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,6 @@
    function Heap(compare = (a, b) => a - b) {
    const arr = [];
    return { push, pop, peek, print };
    return { push, pop, peek };

    function push(v) {
    arr.push(v);
  5. @linfongi linfongi created this gist May 1, 2018.
    51 changes: 51 additions & 0 deletions Heap.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,51 @@
    function Heap(compare = (a, b) => a - b) {
    const arr = [];
    return { push, pop, peek, print };

    function push(v) {
    arr.push(v);
    bubble();
    }

    function pop() {
    const top = peek();
    const last = arr.pop();
    if (arr.length > 0) {
    arr[0] = last;
    sink();
    }
    return top;
    }

    function peek() {
    return arr[0];
    }

    function bubble() {
    let i = arr.length - 1;
    let p = (i - 1) >> 1;

    while (i !== 0 && compare(arr[i], arr[p]) < 0) {
    [arr[i], arr[p]] = [arr[p], arr[i]];
    i = p;
    p = (i - 1) >> 1;
    }
    }

    function sink() {
    let i = 0;
    for (;;) {
    let next = i;
    if (i * 2 < arr.length && compare(arr[i * 2], arr[i]) < 0) {
    [arr[i * 2], arr[i]] = [arr[i], arr[i * 2]];
    next = i * 2;
    }
    if (i * 2 + 1 < arr.length && compare(arr[i * 2 + 1], arr[i]) < 0) {
    [arr[i * 2 + 1], arr[i]] = [arr[i], arr[i * 2 + 1]];
    next = i * 2 + 1;
    }
    if (next === i) return;
    i = next;
    }
    }
    }