Batch processing in increase-key function using binary heap

Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one node, then we have to traverse paths from the node towards the children to re balance the heap. If we want to increase the keys of five nodes in the heap, we need to call the increase-key function five times. Is it possible to call only one increase-key function and perform increase-key on five nodes simultaneously?

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.

StackExchange Computer Science Q#3163, answer score: 5