1 | "use strict";
|
2 |
|
3 | Object.defineProperty(exports, "__esModule", {
|
4 | value: true
|
5 | });
|
6 |
|
7 |
|
8 | class Heap {
|
9 | constructor() {
|
10 | this.heap = [];
|
11 | this.pushCount = Number.MIN_SAFE_INTEGER;
|
12 | }
|
13 |
|
14 | get length() {
|
15 | return this.heap.length;
|
16 | }
|
17 |
|
18 | empty() {
|
19 | this.heap = [];
|
20 | return this;
|
21 | }
|
22 |
|
23 | percUp(index) {
|
24 | let p;
|
25 |
|
26 | while (index > 0 && smaller(this.heap[index], this.heap[p = parent(index)])) {
|
27 | let t = this.heap[index];
|
28 | this.heap[index] = this.heap[p];
|
29 | this.heap[p] = t;
|
30 |
|
31 | index = p;
|
32 | }
|
33 | }
|
34 |
|
35 | percDown(index) {
|
36 | let l;
|
37 |
|
38 | while ((l = leftChi(index)) < this.heap.length) {
|
39 | if (l + 1 < this.heap.length && smaller(this.heap[l + 1], this.heap[l])) {
|
40 | l = l + 1;
|
41 | }
|
42 |
|
43 | if (smaller(this.heap[index], this.heap[l])) {
|
44 | break;
|
45 | }
|
46 |
|
47 | let t = this.heap[index];
|
48 | this.heap[index] = this.heap[l];
|
49 | this.heap[l] = t;
|
50 |
|
51 | index = l;
|
52 | }
|
53 | }
|
54 |
|
55 | push(node) {
|
56 | node.pushCount = ++this.pushCount;
|
57 | this.heap.push(node);
|
58 | this.percUp(this.heap.length - 1);
|
59 | }
|
60 |
|
61 | unshift(node) {
|
62 | return this.heap.push(node);
|
63 | }
|
64 |
|
65 | shift() {
|
66 | let [top] = this.heap;
|
67 |
|
68 | this.heap[0] = this.heap[this.heap.length - 1];
|
69 | this.heap.pop();
|
70 | this.percDown(0);
|
71 |
|
72 | return top;
|
73 | }
|
74 |
|
75 | toArray() {
|
76 | return [...this];
|
77 | }
|
78 |
|
79 | *[Symbol.iterator]() {
|
80 | for (let i = 0; i < this.heap.length; i++) {
|
81 | yield this.heap[i].data;
|
82 | }
|
83 | }
|
84 |
|
85 | remove(testFn) {
|
86 | let j = 0;
|
87 | for (let i = 0; i < this.heap.length; i++) {
|
88 | if (!testFn(this.heap[i])) {
|
89 | this.heap[j] = this.heap[i];
|
90 | j++;
|
91 | }
|
92 | }
|
93 |
|
94 | this.heap.splice(j);
|
95 |
|
96 | for (let i = parent(this.heap.length - 1); i >= 0; i--) {
|
97 | this.percDown(i);
|
98 | }
|
99 |
|
100 | return this;
|
101 | }
|
102 | }
|
103 |
|
104 | exports.default = Heap;
|
105 | function leftChi(i) {
|
106 | return (i << 1) + 1;
|
107 | }
|
108 |
|
109 | function parent(i) {
|
110 | return (i + 1 >> 1) - 1;
|
111 | }
|
112 |
|
113 | function smaller(x, y) {
|
114 | if (x.priority !== y.priority) {
|
115 | return x.priority < y.priority;
|
116 | } else {
|
117 | return x.pushCount < y.pushCount;
|
118 | }
|
119 | }
|
120 | module.exports = exports["default"]; |
\ | No newline at end of file |