#techlearners
Decrease key Operation
Decrease key of element x to k.
Case 0: min-heap property not violated.
decrease key of x to k
change heap min pointer if necessary
Case 1: parent of x is unmarked.
decrease key of x to k
cut off link between x and its parent
mark parent
add tree rooted at x to root list, updating heap min pointer
Case 2: parent of x is marked.
decrease key of x to k
cut off link between x and its parent p[x], and add x to root list
cut off link between p[x] and p[p[x]], add p[x] to root list
If p[p[x]] unmarked, then mark it.
If p[p[x]] marked, cut off p[p[x]], unmark, and repeat.
Delete Key Operation
Delete node x.
Decrease key of x to -.
Delete min element in heap.
TECHLEARNERS BY NEERAJ SAXENA
www.techlearners.co.in
8 дек 2020