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?

Nicolas Rinaudo
  • 809
  • 1
  • 7
  • 11
  • 14
    Read the Wikipedia page on priority queues (http://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 '14 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 '14 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 02 '18 at 08: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 02 '21 at 07:51

4 Answers4

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.

ratchet freak
  • 25,706
  • 2
  • 62
  • 97
  • 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 '14 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 02 '18 at 09: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.

Chihung Yu
  • 218
  • 2
  • 4
  • 1
    Note that at the summary of the page you linked to, priority queue itself is called a *data structure*. – Alexey Apr 02 '18 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.

Nir Friedman
  • 1,427
  • 9
  • 11
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.

Kellen Stuart
  • 216
  • 1
  • 8
  • 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 '21 at 22:02