Batch processing in increase-key function using binary heap
If $P$ is the number of processing units available, consider $P$-ary heaps¹. When descending to perform some operation on a set of keys, you can fork whenever keys lead to different children. If the heap is balanced, this results in independent taks for a uniformly chosen set of keys (and sufficiently big $n$) after having descended a constant number of levels (claim).

The above can only be expected to work well on shared memory systems. As soon as you have NUMA or distributed memory, you want to assign one subtree to every processing unit (and its memory). I suggest you give the root $P$ children, each of which is an (arbitrary) heap in its own right. All operations are send as messages to the corresponding subtree's processing unit. Operations that need the subtrees to interact block the root.




I think $P$ would be the correct branching degree, but you'd have to do some analysis and/or experiments.