How to implement a Binary Heap in JavaScript

Binary Heap, JavaScript, data structures

Here is a reference implementation for a Binary Heap in JavaScript:

BinaryHeapTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
function BinaryHeap(cmp) {
  this.cmp = cmp;
  this.nodes = [];
}
function heapInsert(array, item, cmp = defaultCmp) {
  if (!cmp) cmp = defaultCmp;
  array.push(item);
  return _siftDown(array, 0, array.length - 1, cmp);
}
function heapExtract(array, cmp = defaultCmp) {
  let lastEl, returnItem;
  lastEl = array.pop();
  if (array.length) {
    returnItem = array[0];
    array[0] = lastEl;
    _siftUp(array, 0, cmp);
  } else {
    returnItem = lastEl;
  }
  return returnItem;
}
function heapPushPop(array, item, cmp = defaultCmp) {
  let _ref;
  if (array.length && cmp(array[0], item) < 0) {
    _ref = [array[0], item], item = _ref[0], array[0] = _ref[1];
    _siftUp(array, 0, cmp);
  }
  return item;
}
function heapReplace(array, item, cmp = defaultCmp) {
    let returnItem;
    returnItem = array[0];
    array[0] = item;
    _siftUp(array, 0, cmp);
    return returnItem;
}
function _siftDown(array, startPos, pos, cmp = defaultCmp) {
    let newItem, parent, parentPos;
    
    newItem = array[pos];
    while (pos > startPos) {
      parentPos = (pos - 1) >> 1;
      parent = array[parentPos];
      if (cmp(newItem, parent) < 0) {
        array[pos] = parent;
        pos = parentPos;
        continue;
      }
      break;
    }
    return array[pos] = newItem; // returns newItem and assigns it to array[pos]
}
function _siftUp(array, pos, cmp = defaultCmp) {
    let endPos = array.length;
    let startPos = pos;
    let newItem = array[pos];
    let childPos = 2 * pos + 1;
    while (childPos < endPos) {
      let rightPos = childPos + 1;
      if (rightPos < endPos && !(cmp(array[childPos], array[rightPos]) > 0 )) {
        childPos = rightPos;
      }
      array[pos] = array[childPos];
      pos = childPos;
      childPos = 2 * pos + 1;
    }
    array[pos] = newItem;
    return _siftDown(array, startPos, pos, cmp);
}
function updateItem(array, item, cmp = defaultCmp) {
  let pos = array.indexOf(item);
  if (pos === -1) return;
  _siftDown(array, 0, pos, cmp);
  return _siftUp(array, pos, cmp);
}
BinaryHeap.insert = heapInsert;
BinaryHeap.updateItem = updateItem;
BinaryHeap.extract = heapExtract;
function defaultCmp(x, y) {
  return x < y ? -1 : x > y ? 1 : 0;
}
BinaryHeap.prototype.insert = function(item) {
  return heapInsert(this.nodes, item, this.cmp);
};
BinaryHeap.prototype.extract = function() {
  return heapExtract(this.nodes, this.cmp);
};
BinaryHeap.prototype.replace = function(item) {
 return heapReplace(this.nodes, item, this.cmp);  
};
BinaryHeap.prototype.contains = function(item) {
  return this.nodes.indexOf(item) !== -1;  
};
BinaryHeap.prototype.size = function() {
  
};
BinaryHeap.prototype.isEmpty = function() {
  return true;
};
BinaryHeap.prototype.pushpop = function(item) {
  return heapPushPop(this.nodes, item, this.cmp);  
};
BinaryHeap.prototype.clone = function() {
  let heap;
      heap = new BinaryHeap();
      heap.nodes = this.nodes.slice(0);
      return heap;
};
BinaryHeap.prototype.peek = function() {
  return this.nodes[0];  
};
BinaryHeap.prototype.toArray = function() {
  return this.nodes.slice(0);
};
BinaryHeap.prototype.updateItem = function(x) {
  return updateItem(this.nodes, x, this.cmp);
};

Tests can be found at REPL.it