Binary heap
If you were to implement a priority queue using a regular list, you would essentially have to maintain a sorted list (sorted by priority). This would mean the following:
- insertions would be O(n) for sure as you would need to go through an already sorted list trying to find the right place then doing the insertion.
- removal is from the "front" of the queue, so depending on how you do your implementation, this can be potentially O(n) also.
This is not very efficient. If we were to create our priority queue in this manner, we would not be able to get a very good run time to our sort.
The interesting thing about a priority queue is that we really don't care where any value other than the one with the highest priority is. We care about that... and we want to be able to find it and remove it quickly but all other values can be essentially anywhere.
A binary heap is a data structure that can help us do this.