If both could be implemented with the other, what are the differences between priority queues and binary heaps?

Question

I've red that a binary heap can be implemented using a priority queue. I've also red the opposite, that a priority queue can be implemented using a binary heap.

This seems strange to me as conceptually they are different: a priority queue is a linear data structure with a priority assigned to each element, whereas a binary heap is a binary tree whose nodes are arranged in a certain way.

Is one more fundamental than the other in the sense that it would be better to build one from the other and not the other way around? When thinking about it or coding, what are the benefits and drawbacks of one over the other?

Is it better (in terms of space used or runtime of operations) to not implement one using the other, and that it's often done because most programing languages have one built in but not the other?

Answer 1

Based on standard usage of the terms, a heap is a specific data structure, with a specific representation in memory. A priority queue is an abstract data type: it identifies some operations that must be supported by the data structure, but does not itself describe any particular data structure. You can use a heap to implement the priority queue operations. There are also other ways to implement a priority queue.

You link to a Stack Overflow post that talks about implementing a min heap using priority_queue, but I recommend that you disregard it, as it is only likely to cause confusion. They appear to be using the term "min heap" in an imprecise sense that fails to make a careful distinction between a data structure and an abstract data type. I can see why you were confused after reading it.

Answer 2

A priority queue implemented with a binary heap has worst case behaviour if you add random elements and repeatedly remove the largest element: Say you start with 1,000 random items, then one million times you add a random element and remove the largest one. You will end up with lots of small elements, making adding a random element the worst case.

You get around this by implementing it with two binary heaps: When you find out that adding items is expensive, you create binary heap #2 and add all items that are larger than the largest item of binary heap #1 to heap #2. In an extreme case you could end up with a linked list of binary heaps, with significantly better runtime than a single binary heap.