#techlearners
BINOMIAL-HEAP-EXTRACT-MIN (H)
(1) find the root x with the minimum key in the
root list of H and remove x from the root list of H FIND-MIN-KEY ( )
(2) H’ = MAKE-BINOMIAL-HEAP ( )
(3) reverse the order of the linked list of x’ children
and set head [H’]= head of the resulting list
(4) H = BINOMIAL-HEAP-UNION (H, H’)
return x
end
Time Complexity Extract Minimum Key- O(logn)
BINOMIAL-HEAP-DECREASE-KEY (H, x, k)
key [x] = k
y = x
z = p[y]
while z ≠ NIL and key [y] is less than key [z] do
exchange key [y]= key [z]
exchange satellite fields of y and z
y= z
z= p [y]
endwhile
End
Time Complexity Decrease Key- O(logn)
Binomial-Heap_Delete-Node(H, x)
Step 1: Binomial-Heap_Decrease_Val(H, x, -∞)
Step 2: Min-Extract_Binomial-Heap(H)
Step 3: END
Time Complexity Delete Key - O(logn)
TECHLEARNERS BY NEERAJ SAXENA
www.techlearner...
7 сен 2024