2
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 23 '21 at 2:00
  • $\begingroup$ 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. $\endgroup$ Nov 23 '21 at 11:56
  • $\begingroup$ @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? $\endgroup$
    – northerner
    Nov 23 '21 at 23:51
  • $\begingroup$ 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. $\endgroup$ Nov 25 '21 at 11:01
6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.