CODEWITHSUNDEEP
priority-queue
SuprDewd
SuprDewd

Reputation: 269

Dequeue a Priority Queue

Elements dequeued from a priority queue follow the rule that:

Priority[i] >= Priority[i - 1]

But if many elements have the same priority, in what order should they be dequeued? Should the element that was enqueued first be dequeued first or doesn't it matter? I know this most likely depends on implementation and usage, but I'm looking for the textbook priority queue answer.

Upvotes: 1

Views: 8285

Answers (2)

paxdiablo
paxdiablo

Reputation: 881403

A queue should definitely be FIFO, that is its nature. The priority queue changes the queue aspect slightly in that it lets higher priority items through in preference to lower ones, but that shouldn't change the basic nature of the queue.

I've seen implementations that profess to be queues but do not follow the FIFO rules. I prefer a different name for them to better specify the behaviour (such as priority bags).

In a queue (even a priority one), items with the same priority should be extracted in the same order they were inserted.

In other words, inserting A2 B2 C2 D1 (number is priority) should result in the processing as D1 A2 B2 C2.

Upvotes: 1

Joe
Joe

Reputation: 42627

There isn't a textbook answer. Absent any other information, it could be done as a straight FIFO (within items of the same priority), or undefined, or other behavior.

Other implementations provide the enqueuer the ability to specify additional information that can be used during dequeue to break ties.

Upvotes: 0

Related Questions