`peek_key` function was lost
Closed this issue · 5 comments
After reading the source code, I see peek_key needs running max in buckets, which is now removed. Could peek_key perhaps be implemented behind a feature flag that would enable running max?
Oops - that was indeed a mistake.
But yeah, as you write it requires running max in buckets which I removed after some benchmarking revealed it to not be beneficial. You can sort of do peek_key by first calling constrain and then getting the next key via top. This will require mutating the heap though, and also move the top value, but would that work in your case?
Yes, that works in my case, thank you. Just for the record, it is faster than popping and pushing back the popped value
It would still be great to get support for key peeking (without resetting top), e.g, behind an optional feature flag if it affects performance.
The workaround with calling constrain is not always suitable as it can conflict with monotonicity requirement. Imagine I have an event queue which is naturally monotonic - say, I just push events to be triggered at certain times in the future, and gradually consume them as time goes by. It is monotonic because I never need to push an event which is in the past - however if I call constrain and thus bump top key to a future timestamp, I can no longer push any event that would need to trigger between now and this future timestamp. Sometimes this is not a big deal and you can cap(/floor) the keys of new events, but sometimes this is not acceptable.
Just to note again that nearly every time I find myself reaching out for a monotonic heap, I also need the peek, and usually the workaround with calling constrain is not suitable as it moves the top value (and you don't want it moved unless you end up popping). It is a real shame this functionality was removed - whatever performance impact it had couldn't have been worse than popping and pushing a value back...
There must be a way to implement this with minimal performance impact for the case where peek is not used, or perhaps even put it behind an opt-in feature flag,,. it would make a big difference!