# Priority queue of constant size fit for extraction of K highest priority elements

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:

1. get $K$ highest priority elements (do on them some outside calculation)
2. append $4K$ kind-of-sorted elements back into the priority queue, removing and ignoring the first $K$ elements from step 1
3. 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

One approach: Store them in a sorted array. To do steps 2 and 3, first sort the list of 4K items, then merge the sorted array of N items with the sorted array of 4K items, then discard the 3K lowest. Merging sorted arrays is easy and can be done in a simple linear scan. As Bulat says, this should be cache-friendly. The asymptotic running time is $O(N)$ per cycle, but since it is cache-friendly it might be fast in practice for the sizes you mention.
Another approach: use a self-balancing binary search tree. Then you can remove the highest K items in $O(K \log N)$ time, and you can append 4K items and then remove the lowest 3K in $O(K \log N)$ time, so the asymptotic running time will be $O(K \log N)$ per cycle. Thus in asymptotic terms this is faster, at least when $N$ is sufficiently large. However, due to the need to follow pointers and the resulting impact on the cache, for the size parameters you mention it might be slower in practice.