peek support
dbdr opened this issue · 3 comments
It seems this structure almost does what I need, except that I would need to peek in addition to pop. I tried to push back after pop, but that does not work for me since that modifies the top, and I might need to push a value equal to the previous top (or in between).
Would it be possible to implement peek with this data structure?
Peeking the key could be implemented in O(lg n), but peeking the value would be O(n). Is peeking the key enough for you?
Peeking the key is what I need, and it sounds generally useful to have that if it's significantly cheaper.
By the way, Readme says "Popping an element is O(log m)". Out of curiosity, are you saying that peeking the value would be more expensive than that? I was expecting peek to be cheaper than pop since it needs to find the same data but skips the rearranging part.
It's actually amortized O(log n). Popping involves finding the next bucket and redistributing the elements if necessary, which is O(n), but each element will be moved to another bucket at most O(log n) times. When peeking, we would have to scan through the bucket to find the min value but without the rearranging we cannot ensure we will only "pay" O(log n) per element in total.
Peeking the key is simpler, as the min key for each bucket is stored, as it's just scanning through the list of buckets. I have just released 0.3.8 with peek_key. :)