MinPriorityQueue vs PriorityQueue missing consistency

[manoharreddyporeddy]

Look at below conversation with Claude Sonnet 3.7 that says "This is a common source of confusion with this library"
Please have
1 consistent behavior please, and
2 be backward compatible { compare: ... } with older version, otherwise they will fail - hope this is taken care of

============

You're running into an issue with how the priority queue is initialized in the @datastructures-js/priority-queue package. The problem is with the comparator function.

In version 6.3.2 of this library, the constructor for MinPriorityQueue expects a priority mapper function, not a comparator function. Let me explain:

What's happening:

1. You're trying to use a comparator function: (a, b) => a[1] - b[1]
2. But the library expects a priority mapper: (item) => item[1]

The priority mapper should extract the priority value from each element, and the queue automatically sorts based on these values (lowest to highest for MinPriorityQueue).

Correct version:

function minimumVisitedCells(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Initialize distance array
    const dp = Array.from({ length: m }, () => Array(n).fill(Infinity));
    dp[0][0] = 1;
    
    // Create priority queues for rows and columns
    // Use a mapper function that returns the priority value (the distance)
    const rowPqs = Array.from({ length: m }, () => new MinPriorityQueue(item => item[1]));
    const colPqs = Array.from({ length: n }, () => new MinPriorityQueue(item => item[1]));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Clean up outdated entries in row queue
            while (!rowPqs[i].isEmpty() && 
                  j > rowPqs[i].front()[0] + grid[i][rowPqs[i].front()[0]]) {
                rowPqs[i].dequeue();
            }
            
            // Update distance if we found a better path via row
            if (!rowPqs[i].isEmpty() && 
                (dp[i][j] === Infinity || rowPqs[i].front()[1] + 1 < dp[i][j])) {
                dp[i][j] = rowPqs[i].front()[1] + 1;
            }
            
            // Clean up outdated entries in column queue
            while (!colPqs[j].isEmpty() && 
                  i > colPqs[j].front()[0] + grid[colPqs[j].front()[0]][j]) {
                colPqs[j].dequeue();
            }
            
            // Update distance if we found a better path via column
            if (!colPqs[j].isEmpty() && 
                (dp[i][j] === Infinity || colPqs[j].front()[1] + 1 < dp[i][j])) {
                dp[i][j] = colPqs[j].front()[1] + 1;
            }
            
            // Add current cell to queues if it's reachable
            if (dp[i][j] !== Infinity) {
                rowPqs[i].enqueue([j, dp[i][j]]);
                colPqs[j].enqueue([i, dp[i][j]]);
            }
        }
    }
    
    return dp[m - 1][n - 1] === Infinity ? -1 : dp[m - 1][n - 1];
}

About the example from the docs

The example you shared:

const carsQueue = new PriorityQueue((a, b) => {
    if (a.year > b.year) {
      return -1;
    }
    if (a.year < b.year) {
      // prioratize newest cars
      return 1;
    }
    // with lowest price
    return a.price < b.price ? -1 : 1;
  }
);

This is using PriorityQueue (not MinPriorityQueue or MaxPriorityQueue). The generic PriorityQueue class does accept a comparator function, while the MinPriorityQueue and MaxPriorityQueue classes accept a priority mapper function.

This is a common source of confusion with this library. If you want more control over the comparison, you should use the generic PriorityQueue class. If you just need a simple min or max queue based on a single value, you should use MinPriorityQueue or MaxPriorityQueue with a priority mapper.

============

[manoharreddyporeddy]

Looks like, This library broke all previous solutions on Leet Code @eyas-ranjous
It is not backward compatible { compare: .. } syntax is no more working
Below code used to work, but now it is not working. Please fix this asap. Leetcode updated their library and so its breaking now

===

Code

var getFinalState = function (a, k, mult) {
	const MOD = 10 ** 9 + 7;
	const b = a.slice();
	const pq = new MinPriorityQueue({ compare: (i, j) => b[i] - b[j] || i - j });
	for (let i = 0; i < a.length; i++) pq.enqueue(i);
	for (let i = 0; i < k; i++) {
		const minIndex = pq.dequeue();
		b[minIndex] *= mult;
		b[minIndex] %= MOD;
		pq.enqueue(minIndex);
	}
	return b;
};

[eyas-ranjous]

@manoharreddyporeddy fix is released. v6.3.3