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?
Best Answer
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.