In priority queues also we have to first insert all n elements, which would take nlogn time and then again klogn to extract the top k.
The same goes for sorting. How is priority queue time complexity better than that of sorting for the case that you have mentioned here.
Priority Queues over Sorting
Hello Ankur,
In case sorting time complexity is -> O(nlog(n)+1)
In case of heap time complexity is O(n + Klog(n) )
N -> is time to build heap (it is not nlogn pls check online resources)
Klog(n) to get kth number after construction.
clearly second one is efficent
Thank you for the reply.
In what type of problems should we be using priority queues? (It was mentioned in the video but I couldn’t get it)
check ur assignment u will get sufficient idea about type of problem solvable by heap
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.