data structures using apart from this informationevery node will store two other fields firstthe number of children in the child list of node is stored in degree[xseconda boolean value mark[xindicates whether node has lost child since the last time was made the child of another node of coursethe newly created nodes are unmarked alsowhen the node is made the child of another nodeit becomes unmarked fibonacci heap is generally accessed by pointer called min[hwhich points to the root that has minimum value if the fibonacci heap is emptythen min[hnull as seen in fig roots of all the trees in fibonacci heap are linked together using their left and right pointers into circular doubly linked list called the root list of the fibonacci heap also note that the order of the trees within root list is arbitrary min[ figure linked representation of the fibonacci heap shown in fig in fibonacci heap hthe number of nodes in is stored in [hand the degree of nodes is stored in (noperations on fibonacci heaps in this sectionwe will discuss the operations that can be implemented on fibonacci heaps if we perform operations such as create-heapinsertfind extract-minimumand unionthen each fibonacci heap is simply collection of unordered binomial trees an unordered binomial tree consists of single nodeand an unordered binomial tree ui consists of two unordered binomial trees ui- for which the root of one is made into child of the root of another all the properties of binomial tree also hold for unordered binomial trees but for an unordered binomial tree uithe root has degree iwhich is greater than that of any other node the children of the root are roots of sub-trees ui- in some order thusif an -node fibonacci heap is collection of unordered binomial treesthen (nlog the underlying principle of operations on fibonacci heaps is to delay the work as long as possible creating new fibonacci heap to create an empty fibonacci heapthe create_fib-heap procedure allocates and returns the fibonacci heap object hwhere [ and min[hnull the amortized cost of create_fib-heap is equal to ( inserting new node the algorithm to insert new node in an already existing fibonacci heap is shown in fig in steps and we first initialize the structural fields of node xmaking it its own circular doubly linked list step adds to the root list of in ( actual time nowx becomes an unordered binomial tree in the fibonacci heap in step the pointer to the minimum node of fibonacci heap is updated finallywe increment the number of nodes in to reflect the addition of the new node