Priority Queue

A priority queue is a generalization of both the stack and queue. The difference is in the method of selecting which item to next pop off the data structure. A priority queue usually assigns a number to each item (the priority) and the item with the highest number (priority) is the next to come off. A priority queue that acts like a stack assigns the highest priority to new elements and the queue does exactly the opposite.

The priority queue is used extensively in process scheduling by the operating system; In this setting the priority may be determined by a combination of factors including how much time has elapsed since the process last ran.

Due to the nature of the priority queue it is most often implemented as a binary heap which gives the following complexities (see Big O notation):

Operation Complexity Description
push $O(\log n)$ puts an element into the queue
pop $O(\log n)$ takes the highest priority item out of the queue

How to use or build the structure in Java

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License