Description
A UltraStack is an extended stack that supports six main operations: the standard Stack operations push(x) and pop() and the following non-standard operations:
• get(i): returns the i -th element (from the bottom) on the Stack. • set(i, x): sets the value of the i -th element (from the bottom) on the Stack to x. • max(): returns the maximum value stored on the Stack. • ksum(k): returns the sum of the top k elements on the Stack. The zip file gives an implementation of UltraSlow which implements these operations so that push(x), pop(), get(i) and set(i, x) each run in 𝑂(1) time, but max() and ksum(k) run in 𝑂(𝑛) time.
You have to complete the implementation of UltraFast that implements all six operations. For UltraFast, the running time for get(i) and max() must be 𝑶(𝟏), and for push(x), pop(), set(i, x), and ksum(k) running time must not exceed 𝑶(𝐥𝐨𝐠𝒏). As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook.
Don’t forget to also implement the size() and iterator() methods. The iterator() method returns an Iterator that iterates over the values in order, starting at the bottom and ending at the top of the Stack. Think carefully about your solution before you start coding.
Here are two hints:
1. Storing the partial summations and the partial maximums can save a lot of computation when you update an element in the Stack.
The following figure (on the next page) might help you better understand the idea.
2. Complete binary trees are much simpler to store implicitly using arrays. Heaps use the same idea to store the elements.
