Answer to Question #246978 in Algorithms for Roy

Question

Explain the use of the binary heap as an effective implementation for a priority queue .

Answer 1

As the first element in the min-heap is always the smallest one the binary heap may be used as an implementation of a priority queue. The operation of adding an element to the priority queue is simply the operation of insertion into the heap (with the following reordering to keep heap property) and pulling is realised as removing the first element from the min-heap. As the time complexity of both, adding and removing to/from the heap is O(n log n), this implementation of the priority queue is very effective.