0

The documentation for std::priority_queue states the complexity of the push operation as:

Logarithmic number of comparisons plus the complexity of Container::push_back.

And by default uses std::vector as the underlying container. However, push_back can only push elements to the end of the vector, while in a priority queue one might need to add elements somewhere in the middle of the vector, in which case all elements that follow have to be shifted to the right. In the worst case, when adding an element at the beginning, the push operation would incur the full O(n) cost. So how does the priority queue do it in logarithmic time? Why does it use a vector by default as opposed to some "easy insert and find" container such as a heap?

user207421
  • 305,947
  • 44
  • 307
  • 483
Wais Kamal
  • 5,858
  • 2
  • 17
  • 36

1 Answers1

3

while in a priority queue one might need to add elements somewhere in the middle of the vector, in which case all elements that follow have to be shifted to the right

No. The right shift does not occur.

The new element is added to the end, at index i: O(1)

Then its priority is compared to its parent at index i/2 and swapped if of higher priority.

If a swap occurs, compare the next parent.

Repeat above 2 steps until at at index 0. O(log(i))

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • This way it would mess up the order. In the example you've given, the parent you swapped the last element with (in step 2) will incorrectly end up being the last element in the queue. – Wais Kamal Oct 22 '21 at 04:55
  • 1
    @WaisKamal Yes, it is the last element in the array, but not the last element in priority. The array does _not_ hold the items in priority order. `array[0]` is highest, `array[1]` or `array[2]` is next, both are lower than `array[0]`. – chux - Reinstate Monica Oct 22 '21 at 04:57
  • 1
    @WaisKamal A binary heap is ***not*** a fully ordered set. Please look [here](https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation) for a good description of how they work. The assumptions you're making are flat-out wrong. – pjs Oct 22 '21 at 04:58
  • 1
    @WaisKamal You need to get out of your sorted-list mentality. It doesn't work that way. If it did, the documented behaviour would be impossible, and the data structure would be indistinguishable from a sorted vector ... and not much use. – user207421 Oct 22 '21 at 04:58
  • @chux-ReinstateMonica you are absolutely right, that's the point I was missing. Thanks a lot! – Wais Kamal Oct 22 '21 at 05:03
  • 1
    @WaisKamal Keep in mind its takes O(1) to remove/report the highest prioty item at `index = 0`, then a check of its children at `index * 2 + 1` and `index * 2 + 2` to find which one to move up, then repeat of that to find the child's replacement and so on. All this is then O(log(n)) work. – chux - Reinstate Monica Oct 22 '21 at 05:08
  • Definitely, yes. But I just noticed something: whenever I add an element to the queue and print the elements it contains, the elements are always sorted. Why does this happen? Or is it more appropriate to ask in another question? – Wais Kamal Oct 22 '21 at 05:15
  • 2
    @WaisKamal I reccomend you post the _compilable_ code you used to "whenever I add an element to the queue and print the elements it contains" and why you concluded "the elements are always sorted" as a new question as to the "why". Posting exact input used, output seeen, output expected makes for a good question. Hint: did accessing the priority queue elements one by one take the class O(1) time each? – chux - Reinstate Monica Oct 22 '21 at 05:18
  • 1
    Thank you, I got it. The problem was that I was repeatedly using `pop` to iterate through the queue, which heapifies the tree every time it is called. – Wais Kamal Oct 22 '21 at 05:27