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

Question

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