What is the difference between a heap and a priority queue?
A heap is the way the values are stored. A priority queue is the thing you use. The priority queue is usually built on top of a heap.
import heapq
tasks = [(3, "write docs"), (1, "fix bug"), (2, "review pull request")]
heapq.heapify(tasks)
print(tasks[0]) # (1, 'fix bug')
So what is the difference? Here is the plainest way to say it.
A heap is a shape of data, not just for trees. It is a list where every parent is smaller than its children, or bigger than its children, depending on which kind you want. That rule means the most important value is always at the front of the list, so you can get it in constant time.
A priority queue is a set of items where each one has a priority, and the one that comes out is always the one with the highest priority. It is a promise about how the queue behaves, not about how the values are stored inside.
the thing what it is
-------------- --------------------------------------------------
a heap a way of arranging values so the best one is first
a priority a queue that always gives back the most important
queue item first
And why is a heap the right thing to build a priority queue on? Because of the cost of the operations. A priority queue needs three things. Put an item in, take the most important item out, and look at the most important item without taking it out.
the operation a heap a plain sorted list
------------------------- --------- -------------------
put an item in O(log n) O(n)
take the best one out O(log n) O(n)
look at the best one O(1) O(1)
And that is the whole reason. A sorted list gives you the best item quickly, but putting a new item in the right place means moving everything after it. A heap lets you put a new item in at the end and then sift it up, which is only a log n steps.
And the tie breaker is worth knowing about. If two items have the same priority then you have to say which one comes first, or the order would be random. In Python you put the priority first and then something to break the tie, like the time the job was added.
So the rule to remember is this. The heap is the storage and the priority queue is the behaviour that you want, and one heap can serve many different priority queues.
The next two questions in this topic show the push and pop and how to build a max heap.