A Sorted Design

An unsorted linked list and an unsorted array both make peek and remove $O (n)$ , because the highest-priority element could be anywhere, and finding it is a scan. So keep the elements sorted. Then the highest-priority element is always in the same place. Put it in the last filled slot. Since the highest-priority element is the smallest, the array is sorted from largest to smallest.

peek: Read the last filled slot. That is $O (1)$ .
remove: Clear the last filled slot and shrink the size. Nothing shifts, because the element comes off the end. That is $O (1)$ .
add: Binary search finds where the new element belongs, in $O (lo g n)$ . But to put it there, every element after that slot shifts one slot right. That is $O (n)$ .

A sorted linked list would cost the same. It would keep the highest-priority element at its head, so peek and remove are $O (1)$ . Its add would scan for the right position, which is $O (n)$ . Binary search does not help a linked list.

The costs side by side

Operation	unsorted linked list	unsorted array	sorted array
`size`	$O (1)$	$O (1)$	$O (1)$
`add`	$O (1)$	$O (1)$ amortized	$O (n)$
`peek`	$O (n)$	$O (n)$	$O (1)$
`remove`	$O (n)$	$O (n)$	$O (1)$

Every design has at least one $O (n)$ operation. A design that does no ordering work on add has to search on remove, and a design that keeps the sequence sorted has to shift elements on add. So adding $n$ elements and then removing all $n$ costs $O (n^{2})$ on every flat design: the $n$ operations on the expensive side each cost up to $O (n)$ .

Restricting access did not help

As with the set, a narrow interface does not make a search cheaper. A stack’s top and a queue’s front are defined by position, so reaching them is $O (1)$ . A priority queue’s highest-priority element is defined by its value, and in an unordered sequence, finding an element by its value is a search.