-
Notifications
You must be signed in to change notification settings - Fork 187
/
NodeHeap.js
123 lines (98 loc) · 2.54 KB
/
NodeHeap.js
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
/**
* Based on https://github.com/mourner/tinyqueue
* Copyright (c) 2017, Vladimir Agafonkin https://github.com/mourner/tinyqueue/blob/master/LICENSE
*
* Adapted for PathFinding needs by @anvaka
* Copyright (c) 2017, Andrei Kashcha
*/
module.exports = NodeHeap;
function NodeHeap(data, options) {
if (!(this instanceof NodeHeap)) return new NodeHeap(data, options);
if (!Array.isArray(data)) {
// assume first argument is our config object;
options = data;
data = [];
}
options = options || {};
this.data = data || [];
this.length = this.data.length;
this.compare = options.compare || defaultCompare;
this.setNodeId = options.setNodeId || noop;
if (this.length > 0) {
for (var i = (this.length >> 1); i >= 0; i--) this._down(i);
}
if (options.setNodeId) {
for (var i = 0; i < this.length; ++i) {
this.setNodeId(this.data[i], i);
}
}
}
function noop() {}
function defaultCompare(a, b) {
return a - b;
}
NodeHeap.prototype = {
push: function (item) {
this.data.push(item);
this.setNodeId(item, this.length);
this.length++;
this._up(this.length - 1);
},
pop: function () {
if (this.length === 0) return undefined;
var top = this.data[0];
this.length--;
if (this.length > 0) {
this.data[0] = this.data[this.length];
this.setNodeId(this.data[0], 0);
this._down(0);
}
this.data.pop();
return top;
},
peek: function () {
return this.data[0];
},
updateItem: function (pos) {
this._down(pos);
this._up(pos);
},
_up: function (pos) {
var data = this.data;
var compare = this.compare;
var setNodeId = this.setNodeId;
var item = data[pos];
while (pos > 0) {
var parent = (pos - 1) >> 1;
var current = data[parent];
if (compare(item, current) >= 0) break;
data[pos] = current;
setNodeId(current, pos);
pos = parent;
}
data[pos] = item;
setNodeId(item, pos);
},
_down: function (pos) {
var data = this.data;
var compare = this.compare;
var halfLength = this.length >> 1;
var item = data[pos];
var setNodeId = this.setNodeId;
while (pos < halfLength) {
var left = (pos << 1) + 1;
var right = left + 1;
var best = data[left];
if (right < this.length && compare(data[right], best) < 0) {
left = right;
best = data[right];
}
if (compare(best, item) >= 0) break;
data[pos] = best;
setNodeId(best, pos);
pos = left;
}
data[pos] = item;
setNodeId(item, pos);
}
};