avantgardnerio commented on PR #7192: URL: https://github.com/apache/arrow-datafusion/pull/7192#issuecomment-1673721700
Shout out to @jdavidberger , we've been talking about this a bit, and he's just about convinced me this is a special case that can be implemented with a BinaryHeap after all: 1. fixed size (can be pre-allocated, into a `Vec<Option<T>>` with fixed indexes representing slots in the tree) 2. not removing + inserting, just replacing - log2(limit) 3. always replacing with a "better" value (less than for min heap) so just compare and swap up the tree 4. no need for search the tree if the HashMap(`id_to_val`) stores indexes into the BinaryHeap's `Vec` 5. so potentially no mallocs or frees, just `memcpy`ing when `Sized` is true into the Vec, or a single heap allocation if not @alamb will be pleased 😉 -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
