The contains method currently drains the queue until it finds a match with repeated pop calls, then rebuilds it with push calls. Since heap order is irrelevant here, we can instead traverse the underlying heap array in O(n) time while avoiding rebuilding the heap.
The method could become something like:
contains(cb) { if (typeof cb !== 'function') { throw new Error('PriorityQueue contains expects a callback'); } return this._heap.toArray().some(cb); }
Would be happy to put up a PR for this contains change if that's easier.
If we had better access to the heap then the toArray call could be avoided, making it O(1) space too.
A similar optimisation could be made to the remove method, by filtering the array and then rebuilding the heap from that filtered array in O(n). Only problem with this remove optimisation is that the order of the returned removed elements would no longer be highest priority -> lowest, meaning you would need to sort the return array if that behaviour is desired (O(k log k) where k is the number of removed elements)
The contains method currently drains the queue until it finds a match with repeated pop calls, then rebuilds it with push calls. Since heap order is irrelevant here, we can instead traverse the underlying heap array in O(n) time while avoiding rebuilding the heap.
The method could become something like:
contains(cb) { if (typeof cb !== 'function') { throw new Error('PriorityQueue contains expects a callback'); } return this._heap.toArray().some(cb); }Would be happy to put up a PR for this contains change if that's easier.
If we had better access to the heap then the toArray call could be avoided, making it O(1) space too.
A similar optimisation could be made to the remove method, by filtering the array and then rebuilding the heap from that filtered array in O(n). Only problem with this remove optimisation is that the order of the returned removed elements would no longer be highest priority -> lowest, meaning you would need to sort the return array if that behaviour is desired (O(k log k) where k is the number of removed elements)