DECREASING A KEY

Decreasing a key

The following procedure decreases the key of a node x in a binomial heap H to a new value k.It signals an error if k is greater than x's current key.

BINOMIAL-HEAP-DECREASE-KEY(H, x, k)

1 if k > key[x]

2 then error "new key is greater than current key"

3 key[x] ← k

4 y ← x

5 z ← p[y]

6 while z ≠ NIL and key[y] < key[z]

7 do exchange key[y] ↔ key[z]

8 ▸ If y and z have satellite fields, exchange them, too.

9 y ← z

10 z ← p[y]

Analysis:-

The BINOMIAL-HEAP-DECREASE-KEY procedure takes O(lg n) time. By property

,the maximum depth of x is ⌊lg n⌋, so the while loop of lines 6-10 iterates at

most ⌊lg n⌋ times.

This procedure decreases a key in the same manner as in a binary
min-heap: by "bubbling up" the key in the heap. After ensuring that the new key is in fact no

greater than the current key and then assigning the new key to x, the procedure goes up the

tree, with y initially pointing to node x. In each iteration of the while loop of lines 6-10, key[y]
is checked against the key of y's parent z. If y is the root or key[y] ≥ key[z], the binomial tree is

now min-heap-ordered. Otherwise, node y violates min-heap ordering, and so its key is

exchanged with the key of its parent z, along with any other satellite information. The

procedure then sets y to z, going up one level in the tree, and continues with the next iteration.
The action of BINOMIAL-HEAP-DECREASE-KEY. (a) The situation just
before line 6 of the first iteration of the while loop. Node y has had its key decreased to 7,

which is less than the key of y's parent z. (b) The keys of the two nodes are exchanged, and

the

up one level in the tree, but min-heap order is still violated. (c) After another exchange and

moving pointers y and z up one more level, we find that min-heap order is satisfied, so the

while loop terminates.
continue operations-on-binomial-heap.php