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

1. root node of priority 0
2. left leaf of priority 1
3. right leaf of priority 0

If we call method pop on this queue, we expect to get the new tree:
queue = [1, 2]

ie

1. root node of priority 1
2. 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

1. root node of priority 2
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)

1. Add an export statement for class PriorityQueue in PrimMST.js

export { PriorityQueue }

2. Add a test file PrimMST.test.js containing 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)
})

3. 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.