Priority Queue

Question

Is priority queue work efficiently with sorted array than unsorted array and heap for insertion and deletion operation? Then why do we apply priority queue in heap specially

Comments

Heap : Insertion O(logn), Deletion O(logn)

Sorted array : Insertion O(n), Deletion O(1)

Unsorted array : Insertion O(1), Deletion O(n)

As we are implementing priority queue we will insert and remove the highest priority element, not any random element and searching for any random element is of least concern as we care only about the highest priority, so heap will be best suited for this purpose.

That's what i think.

---

How is deletion in sorted array O(1)? After the element is deleted , don't we need to shift all elements to fill the gap caused due to deletion?