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.