[Suggestion] Can we consider improving the pq with a fixed (max) size?
SheldonWangRJT opened this issue · 13 comments
Meaning if we push more than the max size, the pq will accept the push and then automatically pop the extra item
That would mean that push() would have to have a return value, unless you mean that it would silently pop. I think this is a little outside the scope of a basic priority queue, but would be easy enough to add yourself to a modified version of it. Just add a maxSize parameter to the constructor and check against it in push() and call a silent pop() if it is exceeded.
yeah i meant silently pop, which will make this qp more straightforward in handling problems like nearest N points to origin.. thanks for the quick reply
Thanks for the clarification. I don't know that I want to clutter the base functionality with this. I like how simple it is. It would require doing a check every time someone pushed which would also be a very very slight performance degradation. I have an alternative, what if we added another method called push(_ element: T, withMaxCount: Int). The downside of this approach is withMaxCount would have to be included in every call. Perhaps another alternative is we add maxCount to the constructor as an optional parameter with a default value and have a specialized pushKeepingMax(_ element: T) or a better name... If the current number of items exceeds maxCount in either scenario, we could silently pop count - maxCount number of items.
A while back, I had a need to maintain a top-n filter when processing millions of pushes across multiple cores.
See my fork for an overloaded push with "maxheap" parameter.
Thanks, @reedes. Can you create a pull request to put this in an alternative push() method?
Sure, I'd be happy to do that.
(I vaguely recall thinking about offering one at the time, but was unsure if it was the best approach.)
Ugh, apologies for it not being the cleanest PR. Fortunately there weren't many changes involved.
Hi @reedes and @SheldonWangRJT ,
Please take a look at the version currently in master on GitHub. I ended up making some changes. Unfortunately discarding the lowest priority element when adding a new element will always be inefficient on a binary heap. We would need to change to a min-max heap to make this efficient:
https://en.wikipedia.org/wiki/Min-max_heap
If we are comfortable with it for now, I will push a new release version out.
I see thanks!
Feel free to close this :)
Yep, I limited heap size to reduce performance hit.
Feel free to close. I'll be keeping my 'inverted' fork around until I revisit my app later this year.
Thanks again!
Closed via 1.4.0