Use Comparator in heap.

trekhleb · trekhleb · commit e05d15976548 · 2018-04-12T08:25:19.000+03:00
diff --git a/src/data-structures/heap/MinHeap.js b/src/data-structures/heap/MinHeap.js
@@ -1,7 +1,10 @@
+import Comparator from '../../utils/comparator/Comparator';
+
 export default class MinHeap {
   constructor() {
     // Array representation of the heap.
     this.heapContainer = [];
+    this.compare = new Comparator();
   }
 
   static getLeftChildIndex(parentIndex) {
@@ -85,7 +88,7 @@ export default class MinHeap {
 
     while (
       MinHeap.hasParent(currentIndex) &&
-      this.lessThen(this.heapContainer[currentIndex], this.parent(currentIndex))
+      this.compare.lessThen(this.heapContainer[currentIndex], this.parent(currentIndex))
     ) {
       this.swap(currentIndex, MinHeap.getParentIndex(currentIndex));
       currentIndex = MinHeap.getParentIndex(currentIndex);
@@ -101,14 +104,14 @@ export default class MinHeap {
     while (this.hasLeftChild(currentIndex)) {
       if (
         this.hasRightChild(currentIndex) &&
-        this.lessThen(this.rightChild(currentIndex), this.leftChild(currentIndex))
+        this.compare.lessThen(this.rightChild(currentIndex), this.leftChild(currentIndex))
       ) {
         nextIndex = MinHeap.getRightChildIndex(currentIndex);
       } else {
         nextIndex = MinHeap.getLeftChildIndex(currentIndex);
       }
 
-      if (this.lessThen(this.heapContainer[currentIndex], this.heapContainer[nextIndex])) {
+      if (this.compare.lessThen(this.heapContainer[currentIndex], this.heapContainer[nextIndex])) {
         break;
       }
 
@@ -120,18 +123,4 @@ export default class MinHeap {
   toString() {
     return this.heapContainer.toString();
   }
-
-  compare(a, b) {
-    if (a === b) {
-      return 0;
-    }
-
-    // Min heap may be converted to max heap by simply changing this line to:
-    // a > b ? -1 : 1
-    return a < b ? -1 : 1;
-  }
-
-  lessThen(a, b) {
-    return this.compare(a, b) === -1;
-  }
 }
diff --git a/src/data-structures/priority-queue/PriorityQueue.js b/src/data-structures/priority-queue/PriorityQueue.js
@@ -1,19 +1,21 @@
 import MinHeap from '../heap/MinHeap';
+import Comparator from '../../utils/comparator/Comparator';
 
 // It is the same as min heap except that when comparing to elements
 // we take into account not element's value but rather its priority.
 export default class PriorityQueue extends MinHeap {
   constructor() {
     super();
     this.priorities = {};
+    this.compare = new Comparator(this.comparePriority.bind(this));
   }
 
   add(item, priority = 0) {
     this.priorities[item] = priority;
     super.add(item);
   }
 
-  compare(a, b) {
+  comparePriority(a, b) {
     if (this.priorities[a] === this.priorities[b]) {
       return 0;
     }
