[Bug] PriorityQueue: Inserting previously extracted element does not work

[erikw]

Thanks for providing this module.

I've used the PriorityQueue a bit and noticed something that looks like a bug to me. It seems like if the same element is inserted again after have being extracted once alrady, is not possible.

See this minimal example:

const PriorityQueue = require("algorithms/data_structures").PriorityQueue;

const q = new PriorityQueue();

// Inserting and extracting one time works as expected:
q.insert("a", 1);
console.log(q.isEmpty());
console.log(q.extract());
console.log(q.isEmpty());

// Inserting 'a' again does not work, queue will be empty and nothing to extract:
q.insert("a", 1);
console.log(q.isEmpty());
console.log(q.extract());

The outoupt of this is:

false
a
true
true
undefined

while the expected output is:

false
a
true
false
a

My system:

• node v19.2.0.
• macOS 13.0.1

[Semigradsky]

https://github.com/felipernb/algorithms.js/blob/94b4bb6050b5671f3405af0189369452fda6b4df/src/data_structures/priority_queue.js#L20-L33

Looks like this._priority should be cleared in the extract function. Otherwise, super.insert will not be called.