Priority Queue Delete

Question

Answer 1

When u want to delete the minimal element . . . Then it is the element with least priority or least key value . . . So when u implement it with a max heap the least value will be in the leaf . . So logn to traverse in the worst case . . Here when u delete the leaf there is no need to heapify it. . As by deleting the leaf the heap property will not disturbed .

So answer is C O(logn)

Comments

I think in Heap we order as per priority value..my doubt is min priority is not always with min element.I mn it is not necessary that elemet with min priority will be the minimum element..right??

---

Min priority means . . It will be the last . . So obviously it will be the least value

---

No what i want to say is element and priority i different right?In Priority Queue each element is associated with a priority.So an element with min priority may have more value.

Answer 2

O(logn) when Heap data structure is used..

Comments

Please chk my doubt above

---

See in min heap minimum elements(highest priority) will be at top . when we add any element we need to check priority removibg time no need to check that .

http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

---

@Anirudh SIR , Here my doubt is nothing has mentioned about implementiation of Priority Queue . Then How can we answer it ? If I implement it using Arrays . mentioned here wont it take O(n) ?

How to answer this kind of questions ?

How did you concluded priority queue is used here ? 

plz help me SIR...