In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible:
- get $K$ highest priority elements (do on them some outside calculation)
- append $4K$ kind-of-sorted elements back into the priority queue, removing and ignoring the first $K$ elements from step 1
- remove the $3K$ lowest priority elements (in order to keep constant queue size), and return them
In reality, steps 2-3 will probably be merged somehow and so on, but these are the main implementation details.
I'm looking for the fastest implementation of these actions on a priority queue, for a relatively large $N$ and relatively small $K$ (E.G $K=32$, $N=2048$), that can be tweaked a little if needed (E.G change $N\rightarrow 2500$ if it's faster).
I'm not so familiar with data structures, but here's an assortment of things that might work:
- a sorted array, using $O(1)$ extracts and $O(N)$ merges
- a pairing heap? weird extract times, but $O(1)$ merges
- a more exotic heap type? I've found this question for example, with priority queues that technically are quicker at extracts