Broken? (Results not sorted)

[WilliamOConnell]

When removing objects, it seems like the highest priority object is not always removed first. Example:

https://jsfiddle.net/someoneorsomething/h0spzjy7/15/

I would expect the resulting array to contain all of the objects, sorted by their val. This is mostly the case, but some items show up much later in the removal order than expected. Am I misunderstanding how the library works?

[mreinstein]

On this line:

PQ.queue(queue,{ val: Math.random() });

You're missing the 3rd argument, which should be the priority value.

[WilliamOConnell]

Ah. Maybe this could be made clearer in the documentation. The readme and tests seem to show it working without the third argument.

[mreinstein]

hmm, maybe I'm just mis-remembering the API, haven't looked at this in a while. Will take a more thorough look when I get back to my desk.

[mreinstein]

Sorry for the reply delay. Looking at this now! 👀

[mreinstein]

I think you likely found a bug, somewhere in the underlying heap implementation. Only in some rare number cases do they appear out of order. My minimal repro steps. The included seed random value reproduces the problem on every run:

import Heap from './heap.js';
import Alea from 'alea';


const seed =  0.3880842591560947;
const random = new Alea(seed);


// a is parent b is child. sort in descending order
function comparator (a, b) {
  return a < b ? true : false; // swap true
}

let h = Heap.create(comparator);

const count = 10;

// add count items with random values
for (let i = 0; i < count; i++) {
  const p = random();
  Heap.insert(h, { val: { neat: i, pri: p }, priority: p });
}

// remove the items in order and show results
for (let i = 0; i < count; i++)
  console.log(Heap.poll(h).val);

This results in:

{ neat: 0, pri: 0.9725668889004737 }
{ neat: 3, pri: 0.8349967401009053 }
{ neat: 1, pri: 0.8222610668744892 }
{ neat: 6, pri: 0.7465265986975282 }
{ neat: 5, pri: 0.394229659345001 }
{ neat: 7, pri: 0.6853948319330812 }
{ neat: 4, pri: 0.3161299272906035 }
{ neat: 9, pri: 0.14856508816592395 }
{ neat: 8, pri: 0.13059667288325727 }
{ neat: 2, pri: 0.12049612472765148 }

Clearly this is wrong, since 0.39 should be below 0.68

I'll re-evaluate the heap implementation tomorrow and see if I can figure out what's going wrong.

[mreinstein]

I've tracked the problem down to the poll method within the heap implementation. I'm tempted to re-write this because I think it can be a lot smaller. I'm also not a big fan of the comparator interface; I find it to be a very confusing function to compose, and I never remember the syntax (I have the same problem with javascripts builtin array sort compareFn https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#parameters)

@WilliamOConnell great catch by the way!

[mreinstein]

Resolved via 0c0e129 (will be published to npm as 0.2.0)

Note: I've modified the API quite a bit with this release:

• queue(pq, item, priority) now requires priority as the 3rd argument; no longer optional
• dropped confusing comparator functions; just use the priority argument now
• dropped min-heap priority queues (it always dequeues highest priority value from the pq now). If you need a min-heap, use negative values for priority argument

Let me know if you've got any feedback on this, would love your thoughts before I publish.

Thanks again for the great catch! ❤️

[WilliamOConnell]

Makes sense to me. I like that it's a single file now since that makes it easier to use client-side without a bundler.
I would think it should be a major version bump (1.0.0) though, since it's not backwards-compatible?

Thanks for the fix!

[mreinstein]

makes it easier to use client-side without a bundler

Isn't it amazing how much crap the availability of es modules has removed? It's an amazing time to be a web developer :)

I would think it should be a major version bump (1.0.0)

All version numbers below 1.0.0 are assumed to be semver-major changes. see https://semver.org/#spec-item-4

Thanks for the fix!

Thank you for surfacing this! I'm using this module in my 2d navmesh/pathfinding logic and was wondering why some of the flying creatures were occasionally stuck. You fixed this for me. :D