Deleting a key
It is easy to delete a node x's key and satellite information from binomial heap H in O(lg n)
time. The following implementation assumes that no node currently in the binomial heap has
a key of -∞.
BINOMIAL-HEAP-DELETE(H, x)
1 BINOMIAL-HEAP-DECREASE-KEY(H, x, -∞)
2 BINOMIAL-HEAP-EXTRACT-MIN(H)
The BINOMIAL-HEAP-DELETE procedure makes node x have the unique minimum key in
the entire binomial heap by giving it a key of -∞.It then bubbles this key and the
associated satellite information up to a root by calling BINOMIAL-HEAP-DECREASEKEY.
This root is then removed from H by a call of BINOMIAL-HEAP-EXTRACT-MIN.
Analysis:-
The BINOMIAL-HEAP-DELETE procedure takes O(lg n) time.
operations-on-binomial-heap.php
performance.php?temp-new-window-replacement=true
