46

I always thought that heaps and priority queues were synonyms - an abstract data structure that supports the insert, findMin and deleteMin operations.

Some literature seems to agree with me - Chris Okasaki's Purely Functional Data Structures (chapter 3), for instance.

On the other hand, Wikipedia's heap page defines it as a tree-based data structure, and states that heaps are a concrete implementation of priority queues.

I'm having a hard reconciling this with the fact that I can think of more than one heap implementation - leftist heaps, binomial heaps, splay heaps...

Does the simple fact that a heap can be implemented with different data structures not mean, by definition, that it is an abstract data structure? And if that's the case, is there an actual difference with priority queues?

Improve this question
4
  • 14
    Read the Wikipedia page on priority queues (en.wikipedia.org/wiki/Priority_queue), it says "a priority queue can be implemented with a heap or a variety of other methods such as an unordered array" - and that's actually the answer to your question.
    – Doc Brown
    Aug 31, 2014 at 16:10
  • 4
    Well, not really - it does not help me understand whether a heap is a concrete data structure or an abstract one. I'd tend to say an abstract one, since there are many concrete implementations of a heap. If that's the case, and a priority list and a heap are both abstract data structures with the same properties, then I need help understanding the difference, and saying that one is an possible implementation of the other is not terribly helpful if neither is actually a concrete implementation.
    – Nicolas Rinaudo
    Aug 31, 2014 at 16:17
  • Things are even worse: a binary heap can be implemented as an array or as a binary tree. Fortunately, i haven't heard yet of an array implemented as something else.
    – Alexey
    Apr 2, 2018 at 8:58
  • A data structure can be abstract while still being a concrete implementation of another data structure. It is Abstract in the sense of it defines what operations it supports. In the specific example you gave, A heap is a Binary tree with 2 special properties. It could be thought of as being abstract in this sense. Also, a heap can be used to efficiently implement a priority queue. It doesn't sound contradictory to me.
    – oliverdejohnson
    Nov 2, 2021 at 7:51

4 Answers 4

Reset to default
28

A priority queue can have any implementation, like a array that you search linearly when you pop. All it means is that when you pop you get the value with either the minimum or the maximum depending.

A classic heap as it is typically referred to is usually a min heap. An implementation that has good time complexity (O(log n) on push and pop) and no memory overhead.

Improve this answer
2
  • 5
    Do you mean to say that the difference is that while they share the same operations (findMin, deleteMin, insert), heaps have guaranteed "good" complexities for them where priority queues do not?
    – Nicolas Rinaudo
    Aug 31, 2014 at 21:00
  • 1
    Can't heap also have different implementations with different time complexities (a usual linked binary tree, for example)? Also, the time complexity depends on the memory that is used. If it is a magnetic tape, there will be no O(log(n)) for push and pop, i suppose.
    – Alexey
    Apr 2, 2018 at 9:04
11

This website provides a really clear explanation. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

In short, a priority queue can be implemented using many of the data structures that we've already studied (an array, a linked list, or a binary search tree). However, those data structures do not provide the most efficient operations. To make all of the operations very efficient, we'll use a new data structure called a heap.

Improve this answer
1
  • 2
    Note that at the summary of the page you linked to, priority queue itself is called a data structure.
    – Alexey
    Apr 2, 2018 at 12:36
2

I think that what you wrote about concrete vs abstract is correct. Where you say that splay heaps, binomial heaps are different implementations of heaps though, I think it is more correct to say they are different types of heaps. Heap I think of as a category of implementation that generally guarantees not only the same interface, but also same access times.

You see this with associative maps, and hash tables and binary search trees as well. Bsts and hash tables are both concrete data structures that provide the associative map abstract interface. Red black trees and and avl trees are both balanced bsts, with same big O guarantees and same additional interface (in order traversal). They are different types of trees I would say more than different implementations of trees. They are different but closely related implementations of associative maps.

Improve this answer
0
0

PriorityQueue

A priority queue is an abstract data type. We do not specify the implementation when it is abstract.

Heap

A binary heap is not an abstract data type; it is an actual implementation of a data structure.

Answer

You could implement a PriorityQueue with an unsorted array if you wanted to. Would it be the most efficient way to implement it? No, but it would still be a priority queue.

People get tripped up on the fact that a PriorityQueue's fastest implementation is by using a BinaryHeap; this is because every tutorial will show you the most efficient way to implement one.

So you might the ask:

Why even consider the Priority Queue abstract if there's objectively a best way to implement it?

My response:

Perhaps in the future (with Quantum computing) we'll come up with a more efficient data structure to implement a priority queue. It does us no good to tie it to a concrete data type.

Improve this answer
1
  • We don't really care about the implementation (unless we have to implement it ourselves), just about what functionality it provides, and what the cost of each operation is.
    – gnasher729
    Oct 10, 2021 at 22:02

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