Hmm, your solution for keeping the lowest 2 or more elements still puts the indexing at the end, but it changes the op structure to  %h = op4 (op2 op1 %h) op3 which from a jumping back and forth from beginning to end issue is worse. But it does change the structure in another way that suggests:

%h = map { $_, $h{ $_ } }
         shift sort { $a <==> $b } keys %h;
[download]

(that, by the way, is completely untested. Hmm, testing says it doesn't work, type of arg 1 of shift must be array, not sort. i wasn't aware that sort was a type. I wonder how to do what I want...)