A priority queue is like a regular queue only it has one extra method


This method returns the highest priority item in the queue, and it’s useful for things like sorting when used in conjunction with binary trees.

A naive approach

Now a naive approach to implementing a priority queue would be to use an array and then walk the entire array, every time, looking for the highest priority element.


Things can improve if you sort the array, then ExtractMax() is easy as it is simply the last element


And of course you could do this using a list also, through you would lose the ability to quickly find the max position as you can’t do binary search with a linked list.


So sorted Arrays and LinkedLists are two ways you could implement a priority queue. But if you really want to go fast, what you really need is a binary heap.


These notes were taken from the excellent Coursera data structures course.