4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What would be the point of doing this? Do you expect the improved increase-key to have better time complexity? Or just better actual run time? $\endgroup$ – svick Aug 14 '12 at 13:20
  • $\begingroup$ @Raphael, I have tried to have a linked list that consists of 5 nodes, then send them all at one time to the increase function. Then, change their key values in the heap without rebalancing the heap. Later, I do rebalance starting from the node that located at the lowest level toward the upper level node. This is the only I can do at the moment. I don't have any other idea. $\endgroup$ – has Aug 14 '12 at 19:30
  • $\begingroup$ @svick, I don't think we can improve the time complexity of increase-key function as it is still O(log n) time. However, if we want to improve the actual running time, as well as the number of key comparison, this might be helped. $\endgroup$ – has Aug 14 '12 at 19:33
5
$\begingroup$

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.


  1. I think $P$ would be the correct branching degree, but you'd have to do some analysis and/or experiments.
$\endgroup$
  • $\begingroup$ Thanks Raphael. It seems quite hard to implement as I am not that good at programming esp using shared memory system.:( $\endgroup$ – has Aug 21 '12 at 22:34
  • 1
    $\begingroup$ @has: It's true that this answer can not be considered complete in the sense of "implementation ready"; there is some thinking left to do, especially how to manage rebalancing nicely (in either case). For programming issues, I recommend Stack Overflow. Good luck! $\endgroup$ – Raphael Aug 26 '12 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.