Facebook

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).

Example

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.

Fig 1
Fig 2

 

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

Fig 3
Fig 4
Fig 5

 

Rate this post

Comments

This post currently has one response

Leave a Reply to WilliamVox Cancel reply

Your email address will not be published. Required fields are marked *

Sidebar