Another type of queue is a priority queue. These behave very similarly to standard queues with the exception that rather than being First-In-First-Out, the order in which items are removed is determined by a predefined priority function. There are multiple ways to implement this. A somewhat slow example using Linked Lists is shown below. It is unlikely that anyone would use such an implementation in a production scenario; however, it is a useful learning tool for understanding how Priority Queues work at a conceptual level.
- Insert: $O(n)$
- Extract: $O(1)$
- Find: $O(1)$
priority_function: item1 item2 if item1 and item2 are equal return 0 if item1 should be before item2 return 1 if item1 should be after item2 return -1 insert: new_item for each item in the list: if prority_function(new_item, item) = 1 insert new_item before item break out of loop extract: Remove item from the head of the list and returns it find: Return item from the head without removing it from the list
Click here for build and run instructions