A priority queue is much like a normal queue in that it is an abstract data type for ordering elements. However, in this version of a queue, elements in the list/map are assigned priority values and those with the higher priorities always are served/processed before those with lower ones. In the case that two or more elements have the same priority value, they will be served with as a stack (last-in; first-out order) or a normal queue (first-in; first-out).
Priority queues can be implemented using a heap, among other methods, but it is not only a heap. It must facilitate the following operations that are not required for a basic heap (the first two are fundamental; the others, useful):
- insert an item with a priority value assigned
- retrieve the item with the highest priority
- query the priority of any item in it
- change the priority of an item
- reverse all priorities
- compare the priorities of two items (including how to deal with equal priorities, as mentioned above)
Priority queues are especially useful for when resources are limited. For example, with limited bandwidth on a transmission line from a network router, priorities can ensure that the most important traffic is sent first and is therefore the least likely to be rejected for surpassing maximum capacity. Priorities can also sometimes act as 'weights' on items, helping with projects where strict budgets make it desirable to buy the most important things first.
[ Photo credit Yves Tennevin ]
© BrainMass Inc. brainmass.com May 9, 2024, 2:56 am ad1c9bdddf