Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
3  
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 at 16:10
    
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 at 16:17

2 Answers 2

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.

share|improve this answer
    
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 at 21:00

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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