Two Unsorted Designs

For the stack, the queue, the deque, the set, and the map, we built one implementation on a linked list and another on an array, and for the set a third on a sorted array. A priority queue built the same way would repeat code we have already written, so this time we will not write the classes. We will work out what each design costs, and that is enough to decide whether any of them is good enough.

We will look at three designs, two unsorted and one sorted. All three keep the elements in one sequence, a list or an array. We will call them flat designs. size is $O(1)$ in all three, because each design keeps a count.

An unsorted linked list

Keep the elements in a singly linked list, in no particular order.

• add: The order does not matter, so put the new element at the head. That is $O(1)$.
• peek: The highest-priority element could be anywhere, so finding it means looking at every element. That is $O(n)$.
• remove: The same scan finds the highest-priority node, and unlinking it is $O(1)$. The scan dominates, so remove is $O(n)$.

You might try to speed up peek by keeping a reference to the highest-priority node. Then peek is $O(1)$, but remove is not. Once that node is removed, the reference has to point to the next highest-priority node, and finding that node is another scan.

An unsorted array

Keep the elements in a backing array with a size counter, the way ArrayList does.

• add: Append the new element after the last filled slot. That is $O(1)$ amortized, because of the occasional resize.
• peek: Scan the filled part of the array for the highest-priority element. That is $O(n)$.
• remove: Find the highest-priority element, which is $O(n)$, then use the swap-with-last removal from ArraySet, which is $O(1)$. The search makes remove $O(n)$.

The unsorted array costs the same as the unsorted linked list. In both, add is cheap, and peek and remove are $O(n)$. The cost is the scan: with no order, the highest-priority element could be anywhere.