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...
The fadeToBlack() and fadeFromBlack() methods should always be used in pairs.
Answer the following statement true (T) or false (F)
Microsoft Outlook uses a special file format called a ____ to save your email files, calendar entries, and contacts.
A. Sensitivity level B. mailbox C. data file D. personal storage table
How can change adversely affect your network?
What will be an ideal response?
To ensure continuous playback of a video clip, it must be ____________________, which means that the first 5 or 10 seconds of the clip are downloaded before it begins to play.
Fill in the blank(s) with the appropriate word(s).