0

Trying to figure out which one is more optimal to use and implement.

Another way I was thinking was to use js object. By inserting the priority value (integer/number) as the key in the js object.

Given that when going enumerating a js object in ES6 we can get keys that are integer indices (if applicable), in ascending order. Does ES6 introduce a well-defined order of enumeration for object properties?

We can possible use the js object with integer being keys as priority queue and end up with a runtime of O(n). Object.keys() complexity?

const priorityQueue = {3:1,20:1,10:1,15:1,};
console.log(Object.keys(priorityQueue));
priorityQueue[5]=1;
console.log(Reflect.ownKeys(priorityQueue));
divyanshch
  • 390
  • 5
  • 15
  • 2
    [Which is faster?](https://ericlippert.com/2012/12/17/performance-rant/) – VLAZ Dec 08 '20 at 08:09
  • And how are you going to implement in your object-key-version, when multiple entries with the same priority are enqueued? – FZs Dec 08 '20 at 08:25
  • @FZs I think that can be left to implementation on the use case, we can have either a array or a single value. – divyanshch Dec 08 '20 at 08:33
  • What exactly is your question? – Bergi Dec 08 '20 at 09:37
  • The main question is if my analysis is correct and if it's viable to use object instead of heap to implement a priority queue. If the analysis is correct, it makes Object the better use case since they both would use n space for memory heapsort or object to store, but in this case object would win because of (n) lookup and (1) insert [if no collisions]. – divyanshch Dec 08 '20 at 09:47
  • It seems you've been reading the wrong answer to "*Object.keys() complexity?*". The [proper one](https://stackoverflow.com/a/64912755/1048572) explains how in your use case, `Object.keys()` actually is `O(n log n)`. – Bergi Dec 08 '20 at 09:55
  • That seems justifiable @Bergi. I was also looking at Reflect.ownKeys which is also O(n). https://stackoverflow.com/questions/30076219/does-es6-introduce-a-well-defined-order-of-enumeration-for-object-properties/30919039#30919039 – divyanshch Dec 08 '20 at 09:56
  • No, it isn't, for the very same reasons. (The answer you linked doesn't even mention complexity?) – Bergi Dec 08 '20 at 10:03
  • @Bergi in the link you shared, it says it's dependable and in the case where the keys are "named properties" it is (nLog n). unless i'm reading it wrong. – divyanshch Dec 08 '20 at 10:38
  • 1
    Yes, it depends. You only get `O(n)` for "*sufficiently dense integer-keyed/"indexed" properties*", i.e. basically on an array, but your example `const priorityQueue` doesn't look very dense and I'm not sure why you would expect the general case to be. – Bergi Dec 08 '20 at 10:48
  • @Bergi would it be safe to assume that worst case scenario is O(n log n) if using Object.keys()? If so the next question would be why heapsort when you can just use js Object? Since runtime and data complexity would be the same. `Runtime: (n log n)` `data: (n)` – divyanshch Dec 08 '20 at 23:46
  • 1
    Because a heap allows easy access to elements by index, not by priority - especially access to the first element. Because it works with priorities that are not positive integers. Because it can be iterated in linear time repeatedly. – Bergi Dec 09 '20 at 09:15

0 Answers0