How a Priority Queue a Queue Data Structure. Since it doesn't follow FIFO, shouldn't it be named Priority Array or Priority Linked LIst majorly because Priority Queues don't follow a fashion like a FIFO queue
3 Answers
6
votes
2
votes
If you look at most used implementations, priority queues are essentially heaps - they are arranged in a particular fashion based on priority defined by the programmer - in a simple example, ascending or descending order of integers.
Think of priority queue as a queue where rather than retrieving the elements based on when you add the element, you retrieve them based on how they compare with each other. This comparison can be simply ascending or descending order in your textbook examples. You can understand the ADT from an analogy from another StackOverflow answer:
You're running a hospital and patients are coming in. There's only one doctor on staff. The first man walks in - and he's served immediately. Next, a man with a cold comes in and requires assistance. You add him to the queue and he waits in line for the doctor to become available. Next, a man with an axe in his head comes through the door. He is assigned a higher priority because he is a higher medical liability. So the man with the cold is bumped down in line. Next, someone comes in with breathing problems. So, once again, the man with the cold is bumped down in priority. This is called trigaing in the real world - but in this case it's a medical line.
Implementing this in code would use a priority queue and a worker thread (the doctor) to perform work on the consumable / units of work (the patients).
In real scenario, instead of patients, you might have processes waiting to be addressed by the CPU.
0
votes
In the queue, the natural ordering given by how much time an element waits in a line can be considered the fairest. When you enter in a line waiting for something, first comes first served.
Sometimes, however, there is something special about some elements that might suggest they should be served sooner than others that waited longer. For example, we don’t always read our emails in the order we received them, but often you skip newsletters or “funny” jokes from friends to read work-related messages first.
Likewise, when you design an app or test an app, if there are some bugs, those bugs are prioritized and teams work on those bugs based on bugs severity. First, new bugs are discovered all the time, and so new items will be added to the list. Say a nasty authentication bug is found— you’d need to have it solved by yesterday! Moreover, priority for bugs can change over time. For instance, your CEO might decide that you are going after the market share that’s mostly using browser X, and you have a big feature launch next Friday, so you really need to solve that bug at the bottom within a couple of days.
Priority queues are especially useful when we need to consume elements in a certain order from a dynamically changing list (such as the list of tasks to run on a CPU), so that at any time we can get the next element (according to a certain criterion), remove it from the list, and (usually) stop worrying about fixing anything for the other elements.
That’s the idea behind priority queues: they behave like regular, plain queues, except that the front of the queue is dynamically determined based on some kind of priority. The differences caused to the implementation by the introduction of priority are profound, enough to deserve a special kind of data structure.
