algorithm - 摊销成本/插入和删除

Question

Design a data structure to support the following two types of operations on an initially empty
set S of real numbers:
— Insert(S,x): Inserts number x into S.
— Delete(S): Deletes the largest n/2 numbers from S.

Explain how to implement this data structure with O(1) amortized cost per operation.

这怎么可能？对我来说，似乎每次调用 Insert 时我都需要对数据结构进行排序，如果它没有排序，则删除将花费超过 O(1) 的时间。因此，插入的摊销成本应如下：

插入的摊销成本 = (S + 1)实际成本 + (S + 1)之后的数据结构 - (S - 1)之前的数据结构 = S + 1

这样，摊销成本显然不是 O(1)

标签： algorithm