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

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?

• Some thoughts you can find in the question here: Relation Between Priority Queue, Heap, Tree. Personally I believe a priority queue is an abstract data type (more or less an abstract mathematical model) and the binary heap is a possible implementation of that ADT, using an array. Nov 23 '21 at 2:00
• Adding to the confusion is the fact that priority_queue is the C++ STL wrapper to change the functionality of an array/vector into that of a priority queue, no doubt using the array as binary heap. Nov 23 '21 at 11:56
• @HendrikJan I sort of don't get why people say priority queue is more abstract and a binary heap is an implementation. A language can have both and use both in the same way so wouldn't they be on the same level of abstraction? Nov 23 '21 at 23:51
• In the terminology of Abstract Data Types, a Priority Queue is a data structure that provides the operations IsEmpty, Insert, GetMin, DeleteMin. This is independent from possible implementations, so more or less a (mathematical) model that specifies what data is stored ("a set of items, each with priority"), and what are the rules for the operations ("removes the item with minimal priority"). There are many implementations of such a data type, even an inefficient one like unordered list would do. A wellknown implementation is the Binary Heap, which works like a tree, implemented as array. Nov 25 '21 at 11:01

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.