[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]

algorithms.js/src/data_structures/priority_queue.js

Lines 20 to 33 in 94b4bb6

	insert(item, priority) {
	if (this._priority[item] !== undefined) {
	return this.changePriority(item, priority);
	}
	this._priority[item] = priority;
	super.insert(item);
	}
	extract(withPriority) {
	const min = MinHeap.prototype.extract.call(this);
	return withPriority
	? min && {item: min, priority: this._priority[min]}
	: min;
	}

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