Tied interfaces do tend to take more code than you would at first expect, don't they?

But a slight optimization note. In your DELETE method there is no need to recompute MAX and MIN every time. Just put a check for whether the deleted element is MAX or MIN and then compute them accordingly. This makes DELETE efficient most of the time. Well algorithmically efficient, as you note Perl's tied interface could be snappier...