Priority queue is a type of queue data structure that is neither FIFO nor FILO, but it arranges elements based on their priority values; in a priority queue, each element has a priority value associate with it, the highest priorities are served first or retrieved first before elements with lower priority value.
Priority queue and the heap
To implement the priority queue efficiently, without the need to sort each element based on their priority value every time an element is enqueued (sorting can have a time complexity of or , which is not considered to be efficient), using a heap implementation of the priority queue is often a high efficient choice in terms of time complexity for insertion, removal, and accessing the highest priority element.
Back to parent page: Data Structures and Algorithms