priority queue in JS

Question

I am trying to use a priority Queue for my own data type which is a 3x3 array. The actual code and data type is more complex so I boiled it down to the essentials. Note that the priority queue works well for an integer data type (see output at the end). Everything is self explanatory. Assume the metric function returns a positive integer for a given 3X3 array. I am confused why the dequeueing from the heap does not return the min valued object (or max valued in case I got the comparator backwards but I got the middle value for both). For the data type of integer the priority Queue seems to work correctly as the output shows.

    var r = require('js-priority-queue');



    metric = function (A) {
    N =  A.length;
    if (A[0][1] == 0) return 123;
    if (A[0][1] == 5) return 124;
    if (A[0][1] == 1) return 122;
    if (A[0][1] == 6) return 122;
    return 0;
}


    mComparator = function (m1, m2) {
      ret = metric(m2) - metric(m1);
      return ret;
   }

   mHeap = new r(mComparator);

   nHeap = new r(function (a,b) {
      return b - a;
   })

   A = [[5, 0, 1], [7, 6, 3], [2, 4, 8]];
   B = [[5, 6, 1], [7, 0, 3], [2, 4, 8]];

   C = [[5, 1, 0], [7, 6, 3], [2, 4, 8]];
   D = [[0, 5, 1], [7, 6, 3], [2, 4, 8]];

   console.log("metric(A) -> %d", metric(A));
   console.log("metric(B) -> %d", metric(B));
   console.log("metric(C) -> %d", metric(C));
   console.log("metric(D) -> %d", metric(D));

   mHeap.queue(A);
   mHeap.queue(B);
   mHeap.queue(C);
   mHeap.queue(D);

   X = mHeap.dequeue();
   console.log(X);

   X = mHeap.dequeue();
   console.log(X);

   X = mHeap.dequeue();
   console.log(X);

   X = mHeap.dequeue();
   console.log(X);

   nHeap.queue(123);
   nHeap.queue(124);
   nHeap.queue(122);
   nHeap.queue(122);

   y = nHeap.dequeue();
   console.log(y);


#Output 
metric(A) -> 123
metric(B) -> 122
metric(C) -> 122
metric(D) -> 124
[ [ 5, 0, 1 ], [ 7, 6, 3 ], [ 2, 4, 8 ] ]
[ [ 0, 5, 1 ], [ 7, 6, 3 ], [ 2, 4, 8 ] ]
[ [ 5, 1, 0 ], [ 7, 6, 3 ], [ 2, 4, 8 ] ]
[ [ 5, 6, 1 ], [ 7, 0, 3 ], [ 2, 4, 8 ] ]
122

And how are we supposed to help you when the two most likely sources of error, the js-priority-queue implementation and the metric comparison function, aren't shown? — Jim Mischel
– Jim Mischel, Commented Oct 4, 2018 at 1:19
I installed js-priority-queue using node install. Is there a standard PQ library from JS? Note that the implementation of metric is not needed, I am printing its values and the PQ shouldnt care as long as the values dont change. — Lin Endian
– Lin Endian, Commented Oct 4, 2018 at 1:21
And what happens if you use the integer heap and insert 123, 124, 122, 122 in that order, and then de-queue them? Do you get 122, 122, 123, 124 (or the reverse, if you're building a max-heap)? What happens if you create your own integer comparison function? Do you get the same result? — Jim Mischel
– Jim Mischel, Commented Oct 4, 2018 at 2:04
The integer heap works without any issues, its part of the snippet above. (see the code involving nHeap) — Lin Endian
– Lin Endian, Commented Oct 4, 2018 at 3:37
I'm not yet convinced that the heap works without any issues. Your test does not queue duplicate items. You need to verify that it works as expected with the same input you're supplying to the other test: 123, 124, 122, 122. — Jim Mischel
– Jim Mischel, Commented Oct 4, 2018 at 3:45

Oddwarg · Accepted Answer · 2019-02-24 14:37:05Z

1

If you are using the adamhooper priority queue, then your problem is you are not supplying the comparator correctly. Change your constructor invocations to:

mHeap = new r({"comparator": mComparator});

nHeap = new r({"comparator": function (a,b) {
    return b - a;
}})

And you should start getting expected results. Note that this gives you max-heaps. Since you wanted min-heaps, you should also reverse your comparison order:

mComparator = function (m1, m2) {
    ret = metric(m1) - metric(m2);
    return ret;
}

mHeap = new r({"comparator": mComparator});

nHeap = new r({"comparator": function (a,b) {
    return a - b;
}})

Example code for correctly supplying a comparator is given on the github project's front page, but I see how it could be easy to miss.

answered Feb 24, 2019 at 14:37

Oddwarg

664 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

priority queue in JS

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related