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:  


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
If that's practical question, sorted array may be faster than other approaches. The only O(N) operation you will do is memcpy in L1 cache whose speed using AVX2 is 32 bytes per CPU cycle, i.e. ~100 GB/sec.

You will need 2 arrays to make merge. But then you can use spare space for other computations. More complex data structure may easily run out of L1 cache size.