Abstract:
The complexity of maintaining a set under the operations
Insert, Delete and FindMin is considered. In the comparison
model it is shown that any randomized algorithm with expected amortized cost
t comparisons per Insert and Delete has expected cost at least
comparisons for FindMin. If FindMin is replaced
by a weaker operation, FindAny, then it is shown that a randomized
algorithm with constant expected cost per operation exists; in contrast, it
is shown that no deterministic algorithm can have constant cost per
operation. Finally, a deterministic algorithm with constant amortized cost
per operation for an offline version of the problem is given.
Available as PostScript, PDF, DVI.