PriorityQueue Implementation
Suppose we want to implement the operations of PriorityQueue using a linked-list or an array-based implementation.
Exercise Provide an example of core operations, for each underlying data structure, where the operation cannot be implemented better that $O(n)$.
Hint: We have, generally, two choices: keeping the underlying data ordered (sorted) or not.
Solution
Keeping the underlying data sorted will enable us to perform remove and best in constant time but insert will be $O(n)$ since an array implementation will require shifting elements around and a linked-list implementation will require a linear search to find where to insert.
Keeping the underlying data unordered (unsorted) will require us to perform linear search for finding/removing the best (whether we use array or a linked list implementation).