PriorityQueue: Assuming a priority queue is implemented using List as the backing store, what is the cost of doing an insertion if the list is implemented using an array? Using a linked list? Provide an explanation.
What will be an ideal response?
ArrayLists: O(n). This assumes that the elements are stored in their order of priority. In the worst case, the new element will be inserted at the front of the list, necessitating all the other elements being moved down.
LinkedList: O(n): This assumes that the elements are stored in their order of priority. If the insertion is done at the front or the rear, the insertion time will be constant – O(1), but if it is done anywhere else, there is the cost to find the target position first, hence O(n).
In both cases, if the elements are not stored in order of priority, then insertion time can be O(1), but there will be a higher cost for deletions as the highest priority item would have to be found.
You might also like to view...
A webpage that allows users to enter information is considered a(n) ____ webpage.
A. dynamic B. static C. standard D. interactive
The algorithm ____ is used to find the elements in one range of elements that do not appear in another range of elements.
A. set_union B. set_difference C. set_join D. set_innerjoin