Does priority_queue really produce a Heap?

Question

I am bit confused between Heap and priority_queue in C++ STL. Does priority_queue really produce a Heap?

If we insert elements in order - 5, 1, 10, 30, 20
Output for maxHeap will be: 30, 20, 5, 1, 10
While output for priority_queue will be: 30, 20, 10, 5, 1

What is the reason behind this?

Is priority_queue always sorted?

Related: https://stackoverflow.com/questions/18993269/difference-between-priority-queue-and-a-heap — Carey, Oct 05 '17 at 15:23
What do you mean by "output will be"? `priority_queue` doesn't produce output. It is a data structure. How are you producing the output? — Benjamin Lindley, Oct 05 '17 at 15:24
Why do you care what the *internal* content looks like if it's fulfilling its contract as a priority queue? — pjs, Oct 05 '17 at 17:25
You still failed to tell us what you meant by "output" or "printing the content of". The content of a priority queue is not accessible, but you must remove the top element to get at the next. The remove operation also changes the internal representation of the data structure. — Walter, Oct 05 '17 at 21:30
The reason why I asked this question is this problem - http://www.geeksforgeeks.org/median-of-stream-of-running-integers-using-stl/ . In this when priority_queue is used to implement Heap, it works fine but when I implement heap as array and write heap operations manually, it gives incorrect answers in some cases because of problem described in question. — Anuj Gupta, Oct 06 '17 at 09:40
Perhaps the problem is that your implementation of max heap has a bug in it. But we can't tell, because you didn't post your implementation. — Jim Mischel, Oct 09 '17 at 15:43
This is the whole implementation of problem ( http://www.geeksforgeeks.org/median-of-stream-of-running-integers-using-stl/ ) - https://gist.github.com/anujgupta61/d958d479ff9b0026960252536137bf48 . Sorry for code redundancy. — Anuj Gupta, Oct 10 '17 at 09:11
There is a bug in your `heapifyMaxDown`. It's possible for `max_i` to index off the end of the heap at line 20. The result will be undefined. Also, your `heapifyMaxUp` is wrong. The parent of a node should always be `(n-1)/2`. It doesn't matter whether the node is a right or left child. See http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/ for the simple rules for inserting and removing in a heap. See http://blog.mischel.com/2013/09/30/a-simple-heap-of-integers/ for a working implementation in C# (which you should be able to convert to C++ easily enough). — Jim Mischel, Oct 10 '17 at 22:24
Note that your min heap methods have the same problems as your max heap methods. I suggest you spend some time verifying that your heap implementations work, before you try solving the larger problem. — Jim Mischel, Oct 10 '17 at 22:30
Thank you very much @JimMischel for pointing out bugs in Heap implementation. After correcting those bugs, my problem was solved. — Anuj Gupta, Oct 11 '17 at 16:28

score 3 · Answer 1 · answered Oct 05 '17 at 15:32

Let's see what the standard requires:

[priqueue.cons.alloc]/4:

template <class Alloc> priority_queue(const Compare& compare, const Container& cont, const Alloc& a);

Effects: Initializes c with cont as the first argument and a as the second argument, and initializes comp with compare; calls make_heap(c.begin(), c.end(), comp).

[emphasis added]

Likewise, at [priqueue.members]/1:

void push(const value_type& x);

Effects: As if by:
c.push_back(x);
push_heap(c.begin(), c.end(), comp);

[emphasis added]

...and so on.

Summary

priority_queue is defined in terms of applying heap operations to a collection.

score 0 · Answer 2 · answered Oct 05 '17 at 16:20

Internally, the elements in a priority_queue are stored as a heap. Jerry Coffin’s answer provides the exact wording in the spec that guarantees this.

However, whenever you remove an element from the queue, it removes the largest element from the heap and returns it to you, so the order you see is different than the order in which the elements were originally ordered.

In that sense, the internal heap ordering is there so that the queue can efficiently produce an external ordering of the elements in sorted order. The heap is just an implementation detail that in principle you shouldn’t ever see.

Does priority_queue really produce a Heap?

2 Answers2

Summary