$1$ MinBin$+$Pile

The ExtractMin problem can be summarized this way. It is easy to keep track of the smallest item in a set. We can just have some sort of pointer or index to the smallest item. Every time we insert a new item, check if it is smaller than the current smallest item and update if necessary. However, if we remove the smallest item, now we have to go find the new smallest item, and that can be costly$.$

What if we had the $2$ smallest items on hand? After deleting the smallest item, you would have the new smallest item, but you still need to go find the new second smallest item.

Well, what if we had $k$ smallest items on hand, but we don't replace them after every ExtractMin operation? We wait until there are no more min items. Then, we can find all $k$ smallest items in one costly operation.

The MinBin$+$Pile data structure follows this last idea. A MinBin$+$Pile has a sorted array of up to $k$ items. Let's call this sorted array the MinBin. Items not in the MinBin are stored in an unsorted array called the Pile. When we insert $x,$ we see if $x$ is small enough that it belongs in the MinBin. If not, we add $x$ to the unsorted Pile. To perform an ExtractMin, we just remove the smallest item from the MinBin. If the MinBin is empty, we have to find the $k$ smallest item from the Pile and repopulate the MinBin.

Notes:

Throughout let $n$ denote the current number of items in both the Pile and the MinBin. $($I$.$e$.,$ the value of $n$ changes as we add and remove items from the data structure.$)$

Let $k$ be the maximum size of the MinBin. There may currently be fewer than $k$ items in the MinBin.

In all of the questions below, state your running times in terms of $n$ and $k.$

There is a linear$-$time selection algorithm that finds the $k$ smallest items in an unsorted array. This item is called Select$()$ in CLRS$.($Select works without sorting the array.$)$ You can use this algorithm and the fact that it runs in $O(n)$ time.

Questions:

When we insert $x,$ how do you tell if $x$ belongs in the MinBin or the Pile?

How much actual time does it take to insert in the MinBin? Briefly justify your answer. $($N$.$B$.$: MinBin is a sorted array.$)$

How much actual time does it take to insert in the Pile? Briefly justify your answer. $($N$.$B$.$: the Pile is not sorted.$)$

What is the worst case actual running time for Insert? Briefly justify your answer.

Suppose the MinBin is not empty, you should be able to ExtractMin in constant time. How?

If the MinBin is empty, what is the actual running time to repopulate the MinBin using the Select$()$ algorithm described above? Briefly justify your answer.

What is the worst case actual running time for Extract? Briefly justify your answer.

Suppose we pick $k$ to be $\sqrt[\phantom{2}]{n}.$ We want to have Insert and ExtractMin to run in $O(\sqrt[\phantom{2}]{n})$ amortized time. Think about this for a bit first, then provide an invariant that can be used in an amortized analysis using the accounting method.

Using the invariant you stated above. Justify the $O(\sqrt[\phantom{2}]{n})$ amortized running time for Insert. Make sure that your invariant holds after Insert is complete.

Using the invariant you stated above. Justify the $O(\sqrt[\phantom{2}]{n})$ amortized running time for ExtractMin. Make sure that your invariant holds after ExtractMin is complete.

Modify your analysis to have Insert run in $O(\sqrt[\phantom{2}]{n})$ amortized time and ExtractMin run in $O(1)$ amortized time. $($If you modify the invariant, do state the new invariant.$)$