PriorityQueue Implementation

  • Contrast efficiency of alternative implementation approaches.

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)\Omicron(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. However, the insert will be O(n)\Omicron(n) since an array implementation will require shifting elements around. Even 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 a linear search for finding/removing the best (whether we use an array or a linked list implementation).