How does the token method of amortized analysis work in this example?
Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median).


After partitioning (they assume Quicksort-style partitioning), you can just delete the last $\lceil |S| / 2 \rceil$ elements in the array.


  Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more.


That is a useful intuition, but I feel a little bit besides the point.

Mainly, amortized analysis is about investigating the compound cost of sequences of operations. By dividing the sum by the number of operations we get what we call amortized cost for each operation.

I don't see a specification of such sequences in your problem statement so it may be ill-posed, unless the analysis goes through for all sequences.

So let us check. What is the worst that could happen? Well, probably a sequence of only DELETE-LARGER-HALF operations; consider $n$ elements and a sequence of $m = \lfloor \log_2 n \rfloor$ DELETE-LARGER-HALF operations (after this many, the set is almost empty). Since each operation has linear cost in the number of elements, the total cost then is $\Theta\bigl( \sum_{i=1}^{\log_2 m} 2^i \bigr) = \Theta(m)$ -- fits!

If we wanted to make this sequence more expensive by making individual summands larger, we would need to add INSERT operations. Say we wanted to increase one summand $2^i$ to $2^{i+1}$. We would have to add $2^i$ elements at cost $O(1)$ each, so the compound cost would increase by $2^{i+1}$ -- but $m$ would increase by $2^{i}$! Therefore, the amortized cost would only increase by a constant.

The core observation is this: if an element is to partake in making a DELETE-LARGER-HALF operation expensive (by being there), it has to be INSERTed first. Since DELETE-LARGER-HALF has linear cost, we can not add more than constant cost per element. In combination, this means we will get constant amortized time.

The tokens are a way to formalize this into a proof (which the part you quote does not quite manage to do). The way the tokens are set up and passed around, we see that the cost of any sequence of operations is in $\Theta$ of the total number of tokens we see. We can not possibly see more than $2m$ different tokens so we get an $O(m)$ bound on the compound cost or an $O(1)$ bound on the amortized cost.