Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Queue and Heap are two different data structures, but Priority Queue can be achieved using the Heap DS depending upon the min or max priority.
@Joshua: the question makes no sense, nor do the responses here.
A Priority Queue is an abstract data structure. It's an interface. No implementation information is associated with it. The interface provides pop_element_with_highest_priority() and add(obj, priority). How it's implemented is completely independent of this interface.
Most implementations of a priority queue will do the above operations fast. A binary heap is one such fast implementation, with O(log n) time for both operations.
It makes sense to say a priority queue can be implemented using a heap. A priority queue is an interface that can be implemented by a heap data structure. What does not make sense, however, is to talk about priority queues like they imply some specific algorithm or technique -- it's an interface that can be implemented any number of ways. You can talk about the complexity of operations on a heap, but it doesn't make sense to talk about the complexity of operations on a priority queue, because that would depend on the implementation.
I believe the difference is as follows:
- chad January 11, 2013A priority queue is a queue which the elements are dequeued in priority order. They are a mutable data abstraction. Most importanlty, things can come out first even if they were added after. There is no really "fast" way of finding if an element is in the queue. It is a datastructure that is usefull to use where time matters, so something like a seating chart, we don't want people waiting for a long time, so they have a higher priority.
Complexities are as follows:
insert : O(log n) because an element must be inserted according to the priority, which can be thought of as the "key".
extract_min : O(log n) because red-black tree deletion also requires moving throughout the tree.
A Binary Heap is a special kind of tree. It satifies two things:
1) The priorities of the children are at least as large as the priority of the parent. By this implication, the node at the top as the minimum priority.
2) The different paths from root to leaf differ in height by at most one. At the bottom of the tree there can be some missing nodes, but these are to the right of all the leaves that are present. This isn't always true in a priority queue.
You can find the min element in O(1) time. Extracting it while maintaing the heap itself will take O(lg n) time, inserting will take the same amount as well.
Overall the sorting is faster in a Queue, as tehy should be sorted, but that isn't always the case in the heap.