Skip to content

Commit 138c3d9

Browse files
trekhlebtrekhleb
committed
Refactor MinHeap.
1 parent 062f5a4 commit 138c3d9

5 files changed

Lines changed: 68 additions & 9 deletions

File tree

‎.eslintrc‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77
},
88
"rules": {
99
"no-bitwise": "off",
10-
"no-lonely-if": "off"
10+
"no-lonely-if": "off",
11+
"class-methods-use-this": "warn"
1112
}
1213
}

‎README.md‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,8 +9,9 @@
99
3. [Stack](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/stack)
1010
4. [Hash Table](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/hash-table)
1111
5. [Heap](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/heap)
12-
5. [Trie](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/trie)
13-
6. [Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree)
12+
6. [Priority Queue](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/priority-queue)
13+
7. [Trie](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/trie)
14+
8. [Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree)
1415
* [Binary Search Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/binary-search-tree)
1516

1617
## [Algorithms](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms)

‎src/data-structures/heap/MinHeap.js‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -85,7 +85,7 @@ export default class MinHeap {
8585

8686
while (
8787
MinHeap.hasParent(currentIndex) &&
88-
MinHeap.lessThen(this.heapContainer[currentIndex], this.parent(currentIndex))
88+
this.lessThen(this.heapContainer[currentIndex], this.parent(currentIndex))
8989
) {
9090
this.swap(currentIndex, MinHeap.getParentIndex(currentIndex));
9191
currentIndex = MinHeap.getParentIndex(currentIndex);
@@ -101,14 +101,14 @@ export default class MinHeap {
101101
while (this.hasLeftChild(currentIndex)) {
102102
if (
103103
this.hasRightChild(currentIndex) &&
104-
MinHeap.lessThen(this.rightChild(currentIndex), this.leftChild(currentIndex))
104+
this.lessThen(this.rightChild(currentIndex), this.leftChild(currentIndex))
105105
) {
106106
nextIndex = MinHeap.getRightChildIndex(currentIndex);
107107
} else {
108108
nextIndex = MinHeap.getLeftChildIndex(currentIndex);
109109
}
110110

111-
if (MinHeap.lessThen(this.heapContainer[currentIndex], this.heapContainer[nextIndex])) {
111+
if (this.lessThen(this.heapContainer[currentIndex], this.heapContainer[nextIndex])) {
112112
break;
113113
}
114114

@@ -121,15 +121,15 @@ export default class MinHeap {
121121
return this.heapContainer.toString();
122122
}
123123

124-
static compare(a, b) {
124+
compare(a, b) {
125125
if (a === b) {
126126
return 0;
127127
}
128128

129129
return a < b ? -1 : 1;
130130
}
131131

132-
static lessThen(a, b) {
133-
return MinHeap.compare(a, b) === -1;
132+
lessThen(a, b) {
133+
return this.compare(a, b) === -1;
134134
}
135135
}

‎src/data-structures/priority-queue/PriorityQueue.js‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
import MinHeap from '../heap/MinHeap';
2+
3+
// It is the same as min heap except that when comparing to elements
4+
// we take into account not element's value but rather its priority.
5+
export default class PriorityQueue extends MinHeap {
6+
constructor() {
7+
super();
8+
this.priorities = {};
9+
}
10+
11+
add(item, priority = 0) {
12+
this.priorities[item] = priority;
13+
super.add(item);
14+
}
15+
16+
compare(a, b) {
17+
if (this.priorities[a] === this.priorities[b]) {
18+
return 0;
19+
}
20+
21+
return this.priorities[a] < this.priorities[b] ? -1 : 1;
22+
}
23+
}

‎src/data-structures/priority-queue/__test__/PriorityQueue.test.js‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
import PriorityQueue from '../PriorityQueue';
2+
3+
describe('PriorityQueue', () => {
4+
it('should create default priority queue', () => {
5+
const priorityQueue = new PriorityQueue();
6+
7+
expect(priorityQueue).toBeDefined();
8+
});
9+
10+
it('should insert items to the queue and respect priorities', () => {
11+
const priorityQueue = new PriorityQueue();
12+
13+
priorityQueue.add(10, 1);
14+
expect(priorityQueue.peek()).toBe(10);
15+
16+
priorityQueue.add(5, 2);
17+
expect(priorityQueue.peek()).toBe(10);
18+
19+
priorityQueue.add(100, 0);
20+
expect(priorityQueue.peek()).toBe(100);
21+
});
22+
23+
it('should poll from queue with respect to priorities', () => {
24+
const priorityQueue = new PriorityQueue();
25+
26+
priorityQueue.add(10, 1);
27+
priorityQueue.add(5, 2);
28+
priorityQueue.add(100, 0);
29+
30+
expect(priorityQueue.poll()).toBe(100);
31+
expect(priorityQueue.poll()).toBe(10);
32+
expect(priorityQueue.poll()).toBe(5);
33+
});
34+
});

0 commit comments

Comments
 (0)