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.)
alt Hacker News
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.)