Practice question · Put in order
The manager holds 1024 tasks. Order these operations from cheapest to most expensive.
- Peek at the heap's root to see the most urgent task
- Insert one task into the heap
- Scan an unsorted list of all tasks to find the most urgent
- Compare every task against every other task
- Sort all the tasks by deadline
Hints
- Attach a growth class to each operation first, then evaluate it at 1024.
- The base-2 logarithm of 1024 is 10, so put roughly 1, 10, 1024, 10240 and a million against the five options.
Show the answer
- Peek at the heap's root to see the most urgent task
- Insert one task into the heap
- Scan an unsorted list of all tasks to find the most urgent
- Sort all the tasks by deadline
- Compare every task against every other task
Why
The costs are about 1, 10, 1024, 10240 and a million steps. The peek is constant because the heap keeps the extreme at the root; the scan is linear; sorting adds a logarithmic factor to that; comparing all pairs is quadratic. The whole argument for the heap is the gap between the second and third entries.
Practise Integrated Data-Structure Reasoning
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Integrated Data-Structure Reasoning
- The task manager keeps every task in a hash table, a heap and a list at once. What does that composition buy,…
- Sort each statement about the composed task manager by whether it is a cost or a benefit of the design.
- A task manager keeps tasks in a hash map, a heap and a sorted list. A delete updates two of the three. When…
- Select every edge case the lesson says the task manager should be tested against.
- If three structures each hold their own copy of which tasks exist, any update must change all three or they…