Priority queue in o(n)

#1

Can we build stl priority queue in o(n). because building it by inserting the elements one by one takes o(nlogn ) time.

#2

@gaurav19063 see slide 4 and 5 carefully https://www.cs.bgu.ac.il/~ds122/wiki.files/Presentation09.pdf

#3

@Ishitagambhir i completely undetstood how to implement heap in o(n), it’s not the doubt. my doubt is how to build heap by using c++ stl priority_queue in o(n).

#4

@gaurav19063 a tighter analysis is given on slide 5 which states that the running time of building a max heap is actually O(n)

#5

@Ishitagambhir i don’t think you understood my doubt. Please read all the previous ramayan again and then give answer. it’s about finding the time complexity by using C++ priority_queue STL .

#6

@gaurav19063 how do you plan to change the time complexity of an STL function?

#7

You have a good question and I don’t have an answer to it… so sorry I wasted your time…

#8

@gaurav19063 please mark your doubt as resolved if you dont have any further queries

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.