0

I know about the basics of priority queue, and I wonder can we add an element in the prority queue but after a certain value, as eg:- My array is 2, 5, 7, 11. I want to add 4 but after but after 5, the final array being: 2,5,4,7,11. Is there any other way to do it in O(logn) time?

  • 1
    are you specifically referring to the [`std::priority_queue`](http://en.cppreference.com/w/cpp/container/priority_queue) *adapter* ? If not, this question has little to do with C++ and is more a general algorithm question. – WhozCraig Jan 27 '17 at 10:23
  • Ya, I am referring to std::priority_queue adapter. –  Jan 27 '17 at 10:29
  • Then the answer is you can't. `std::priority_queue` utilizes element placement (and thusly priority fetch order) based solely on the *comparator* used for managing the underlying heap structure. You cannot arbitrarily shove some element in a specific place in the queue. Just use the queue's push member and let it do its job. – WhozCraig Jan 27 '17 at 10:31
  • Are you trying to make sure that the array is sorted at all times? – Jim Mischel Jan 27 '17 at 15:15

1 Answers1

0

Is there any other way to do it in O(logn) time?

It is not possible to insert into an arbitrary position of an array in logarithmic complexity.

It is possible to insert a value into a an array, and move elements around such that heap property is maintained in logarithmic complexity, but that doesn't necessarily result in the final array that you expect here.

eerorika
  • 232,697
  • 12
  • 197
  • 326