How do you efficiently track the "worst element" without something like a max-heap? But yeah, this is a fun algorithm. I think I've seen it before but can't place it, do you remember where you came across it?
Exactly. Keeping a max (or min or sum etc) is easy, if you only ever insert into your structure.
The deletion comes in a big batch, where we don't mind paying a linear cost to prune and rebuild our bucket.
Oh, and in our case it's even simpler: the worst element in our buffer only updates during the pruning phase. By construction, we otherwise only ever insert elements that are better than the worst, so we don't have to update the worst. (Outside of the first k elements that we all take anyway to get started. But if you want, you can handle that as a special case.)