Operations on Binomial Heap – Decrease key


Decrease key refers to reducing the key value of any node.If we want to decrease a key in Binomial heap,we will replace the key with reduced value and will repeatedly exchange the reduced key with the parent in order to restore min-heap property.The running time to perform this operation is O(log n).


Say we want to decrease 50 to 4 in binomial heap given in Fig 1.The steps further followed are given in Fig 2,3,4,5 respectively.

Screen Shot 2014-06-11 at 4.40.39 PM

Fig 1 : Binomial heap before decrease-key operation

Screen Shot 2014-06-11 at 4.42.16 PM

Fig 2 : Replace 50 by 4


4 and 21 are swapped in Fig 3 and 4 and  8 are swapped in Fig 4 in order to retain min-heap property.

Screen Shot 2014-06-11 at 4.43.35 PM

Fig 3 : Swap 3 and 21

Screen Shot 2014-06-11 at 4.44.46 PM

Fig 4 : Swap 4 and 8

Screen Shot 2014-06-11 at 4.45.35 PM

Fig 5 : Binomial heap after decrease-key operation


Short URL: http://tinyit.cc/9b8900
Author: Cusp2207 on June 11, 2014
Category: Computer Science
1 response to “Operations on Binomial Heap – Decrease key”
  1. WilliamVox says:

    Thank you for your forum post.Really looking forward to read more. Fantastic. Shakespear

Leave a Reply for WilliamVox

Last articles