We need to create a data structure that supports the following two operations:

$-$ Insert$($S$,$ x$)-$ inserts $\backslash ($ x $\backslash )$ into set $\backslash ($ S $\backslash )$

$-$ Delete$-$Half$($S$)-$ deletes the largest $\backslash (\backslash$frac$\{|$S$|\}\{2\}\backslash )($rounded up$)$ elements from $\backslash ($ S $\backslash )$ such that any sequence of $\backslash ($ n $\backslash )$ operations takes amortized $\backslash ($ O$($n$)\backslash )$ time when we first start with an empty data structure.

$($a$)$ Describe your data structure and how it performs the operations above.

$($b$)$ Justify why $\backslash ($ n $\backslash )$ operations take $\backslash ($ O$($n$)\backslash )$ amortized time, using any method discussed in lecture. $($If you can't achieve $\backslash ($ O$($n$)\backslash ),$ try to get as close as you can with either an amortized or a worst$-$case algorithm.$)$