data structures using decreasing the value of node the algorithm to decrease the value of node in step if val[ptro( amortized time is given in fig print "errorin the decrease-val_fib-heap (fig )we [end of ifstep set val[ptrv first ensure that the new value is not greater than step set par parent[ptrthe current value of the node and then assign step if par !null and val[ptrval[parthe new value to ptr if either the ptr points to cut (hptrparcascading-cut(hparroot node or if val[ptr>val[par]where par [end of ifis ptr' parentthen no structural changes need step if val[ptrval[min[ ]to be done this condition is checked in step set min[hptr [end of ifhoweverif the if condition in step evaluates step end to false valuethen the heap order has been violated and series of changes may occur firstfigure algorithm to decrease the value of node we call the cut procedure to disconnect (or cutany link between ptr and its parthereby making ptr root if ptr is node that has undergone the following historythen the importance of the mark field can be understood as followscase ptr was root node case then ptr was linked to another node case the two children of ptr were removed by the cut procedure note that when ptr will lose its second childit will be cut from its parent to form new root mark[ptris set to true when cases and occur and ptr has lost one of its child by the cut operation the cut procedurethereforeclears mark[ptrin step of the cut procedure howeverif ptr is the second child cut from its parent par (since the time that par was linked to another node)then cascading-cut operation is performed on par if par is rootthen the if cut(hptrparcondition in step of cascading-cut causes the step remove ptr from the child list of par procedure to just return if par is unmarkedthen step set degree[pardegree[par it is marked as it indicates that its first child has step add ptr to the root list of just been cutand the procedure returns otherwisestep set parent[ptrnull step set mark[ptrfalse if par is markedthen it means that par has now step end lost its second child thereforeptr is cut and cascading-cut is recursively called on par' parent figure algorithm to perform cut procedure the cascading-cut procedure is called recursively up the tree until either root or an unmarked node cascading-cut (hptris found once we are done with the cut (fig and step set par parent[ptrstep if par !null the cascading-cut (fig operationsstep of if mark[ptrfalse the decrease-val_fib-heap finishes up by updating set mark[ptrtrue min[helse cut (hptrparnote that the amortized cost of decrease-val_fibcascading-cut(hparheap is ( the actual cost of decrease-val_fib[end of ifheap is ( time plus the time required to perform step end the cascading cuts if cascading-cut procedure is recursively called timesthen each call of figure algorithm to perform cascade decrease-val_fib-heap (hptrv