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?