1 | "use strict";
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 | function BinaryHeap(cmp) {
|
10 | |
11 |
|
12 |
|
13 |
|
14 |
|
15 | this.cmp = cmp;
|
16 | |
17 |
|
18 |
|
19 |
|
20 |
|
21 | this.array = [];
|
22 | |
23 |
|
24 |
|
25 |
|
26 |
|
27 | this.length = 0;
|
28 | }
|
29 |
|
30 |
|
31 |
|
32 |
|
33 |
|
34 |
|
35 | BinaryHeap.prototype.parentIndex = function(i) {
|
36 | return ((i - 1) / 2) |0;
|
37 | };
|
38 |
|
39 |
|
40 |
|
41 |
|
42 |
|
43 |
|
44 | BinaryHeap.prototype.firstChildIndex = function(i) {
|
45 | return (2 * i) + 1;
|
46 | };
|
47 |
|
48 |
|
49 |
|
50 |
|
51 |
|
52 | BinaryHeap.prototype.bubbleUp = function(pos) {
|
53 | if (pos === 0) {
|
54 | return;
|
55 | }
|
56 |
|
57 | var data = this.array[pos];
|
58 | var parentIndex = this.parentIndex(pos);
|
59 | var parent = this.array[parentIndex];
|
60 | if (this.cmp(data, parent) < 0) {
|
61 | this.array[parentIndex] = data;
|
62 | this.array[pos] = parent;
|
63 | this.bubbleUp(parentIndex);
|
64 | }
|
65 | };
|
66 |
|
67 |
|
68 |
|
69 |
|
70 | BinaryHeap.prototype.insert = function(data) {
|
71 | this.array.push(data);
|
72 | this.length = this.array.length;
|
73 | var pos = this.array.length - 1;
|
74 | this.bubbleUp(pos);
|
75 | };
|
76 |
|
77 |
|
78 |
|
79 |
|
80 |
|
81 | BinaryHeap.prototype.bubbleDown = function(pos) {
|
82 | var left = this.firstChildIndex(pos);
|
83 | var right = left + 1;
|
84 | var largest = pos;
|
85 | if (left < this.array.length && this.cmp(this.array[left], this.array[largest]) < 0) {
|
86 | largest = left;
|
87 | }
|
88 | if (right < this.array.length && this.cmp(this.array[right], this.array[largest]) < 0) {
|
89 | largest = right;
|
90 | }
|
91 | if (largest !== pos) {
|
92 | var tmp = this.array[pos];
|
93 | this.array[pos] = this.array[largest];
|
94 | this.array[largest] = tmp;
|
95 | this.bubbleDown(largest);
|
96 | }
|
97 | };
|
98 |
|
99 |
|
100 |
|
101 |
|
102 | BinaryHeap.prototype.deleteRoot = function() {
|
103 | var root = this.array[0];
|
104 | if (this.array.length <= 1) {
|
105 | this.array = [];
|
106 | this.length = 0;
|
107 | return root;
|
108 | }
|
109 | this.array[0] = this.array.pop();
|
110 | this.length = this.array.length;
|
111 | this.bubbleDown(0);
|
112 | return root;
|
113 | };
|
114 |
|
115 |
|
116 |
|
117 |
|
118 |
|
119 | BinaryHeap.prototype.indexOf = function(data) {
|
120 | for (var i = 0; i < this.array.length; i++) {
|
121 | if (this.array[i] === data) {
|
122 | return i;
|
123 | }
|
124 | }
|
125 | return -1;
|
126 | };
|
127 |
|
128 | module.exports = BinaryHeap;
|