One quick question, as you have mentioned if i use sorted array as priority queue i would need O(n) time to insert and O(1) time to delete_max, so overall to process n jobs its O(n^2), why can't i insert in a binary search way needing O(logn) to insert and take out in O(1) time making it O(nlogn) and we do not have to move to heaps in that case. Am i missing something?
I can't believe how easily he has explained a tricky topic.
ya
hao na ga
One quick question, as you have mentioned if i use sorted array as priority queue i would need O(n) time to insert and O(1) time to delete_max, so overall to process n jobs its O(n^2), why can't i insert in a binary search way needing O(logn) to insert and take out in O(1) time making it O(nlogn) and we do not have to move to heaps in that case. Am i missing something?
Sir could u pls explain operation complexity for 2 dimensional array for priority queue is order n root n...it should be only root n? Please correct
See, root(n) is the complexity for 1 operation. So for n such operations, time complexity will be n*root(n).