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

ExtractMax()

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.

unsorted.PNG

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

sorted-array.PNG

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.

sorted-list.PNG

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.

binary-heap-fast.PNG

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

Advertisements