Repository navigation
[BUG]: method pop in PrimMST.js not working properly #1298
Description
Description
In Graphs/PrimMST.js, the method _shiftDown of class PriorityQueue does not give the correct output when a node must be shifted to a left-child leaf without a right-child "brother", which results in a wrong behavior of method pop.
Expected Behavior
An example of a tree that produces the bug is given by the following array of nodes denoted by their priority:
queue = [0, 1, 2]
ie
- root node of priority 0
- left leaf of priority 1
- right leaf of priority 0
If we call method pop on this queue, we expect to get the new tree:
queue = [1, 2]
ie
- root node of priority 1
- left leaf of priority 2
Actual Behavior
In the case described above, we will get as output a tree represented by:
queue = [2, 1]
ie
- root node of priority 2
- left leaf of priority 1
This violates the properties of the heap (we have 2 > 1 but a parent node should never have a bigger value than any of its children).
Steps to reproduce (if applicable)
- Add an export statement for class PriorityQueue in PrimMST.js
export { PriorityQueue }
- Add a test file
PrimMST.test.jscontaining the following code
import { PriorityQueue} from '../PrimMST.js'
test('Bug in pop method', () => {
// create queue
const queue = new PriorityQueue()
queue.push(0, 0)
queue.push(1, 1)
queue.push(2, 2)
// create expected queue
const expectedQueue = new PriorityQueue()
expectedQueue.push(1, 1)
expectedQueue.push(2, 2)
// result from popping element from the queue
queue.pop()
expect(queue).toEqual(expectedQueue)
})
- Run the tests for PrimMST
npm test -- PrimMST.test.js
Additional information
This is due to the fact that in _shiftDown, the children's priorities are computed under a single try {} catch {} statement, thus the priority of the left child is set to Infinity if the right child does not exist.
Activity
paulinegarelli commentedon Feb 21, 2023
I am working on correcting the bug, refactoring the method
_shiftDownfor a clearer computation of nodes priorities, and adding tests forPrimMSTand thepopmethod.appgurueu commentedon Feb 21, 2023
The priority queue should not be a part of
PrimMST, it should be its own algo (or rather, data structure) with its own implementation and tests and should only be imported and used byPrimMST.Please have a look - it should be possible to merge the PQ used & implemented in
PrimMSTwith our existing PQ implementation: https://github.com/TheAlgorithms/JavaScript/blob/master/Data-Structures/Heap/MinPriorityQueue.jsref: KeyPriorityQueue in separate file TheAlgorithms#1298
feat: add tests for KeyPriorityQueue TheAlgorithms#1298
fix: _shiftDown refactored and corrected TheAlgorithms#1298
fix: use KeyPriorityQueue in PrimMST TheAlgorithms#1298
feat: add test for PrimMST TheAlgorithms#1298
fix: format files TheAlgorithms#1298
paulinegarelli commentedon Feb 22, 2023
I couldn't merge the two implementations because the PQ we use has keys in addition to the priority value to be able to track the nodes of the graph, which none of the already existing implementations have.
So I added this implementation as a new algorithm.
fix: use map for keys and priorities TheAlgorithms#1298
fix: refactor PrimMST and fix bug in PriorityQueue (#1300)