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?

  • 12
    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 '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 2 '18 at 8:58

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.

  • 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
  • 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 '18 at 9:04

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.

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

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.


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