Wednesday, June 18, 2008


Decrease-key (H, x, k)

The above procedure decreases the key of x to k. It uses operation ‘Cut’ and ‘Cascade-Cut’ to maintain any violation.
Step 1 Is greater ?
if (k > key [x]) then
message : “new key is greater than the current key”.
Step 2 Initialization
set key [x]  k
set y  parent [x]
Step 3 Checking, cut off the link, adding to the root list.
if (y  Nil and key [x] < key [y]) then
call to Cut (H, x, y).
call to Cascade-Cut (H, y)
Step 4 Up date min [H] pointer
if (key [x] < key [min [H]) then
set min [H]  x
Step 5 Return at the point of call

No comments: