amortized analysis in order to lower this time boundthe time required to perform the decreasekey operation must be improved -heapswhich were described in section give an (logd | |time bound for the decreasekey operation as well as for insertbut an ( logd | |bound for deletemin by choosing to balance the costs of |edecreasekey operations with |vdeletemin operationsand remembering that must always be at least we see that good choice for is max( | |/|vthis improves the time bound for dijkstra' algorithm to (|elog( | |/| | |the fibonacci heap is data structure that supports all the basic heap operations in ( amortized timewith the exception of deletemin and removewhich take (log namortized time it immediately follows that the heap operations in dijkstra' algorithm will require total of (| |vlog | |time fibonacci heaps generalize binomial queues by adding two new conceptsa different implementation of decreasekeythe method we have seen before is to percolate the element up toward the root it does not seem reasonable to expect an ( amortized bound for this strategyso new method is needed lazy mergingtwo heaps are merged only when it is required to do so this is similar to lazy deletion for lazy mergingmerges are cheapbut because lazy merging does not actually combine treesthe deletemin operation could encounter lots of treesmaking that operation expensive any one deletemin could take linear timebut it is always possible to charge the time to previous merge operations in particularan expensive deletemin must have been preceded by large number of unduly cheap mergeswhich were able to store up extra potential cutting nodes in leftist heaps in binary heapsthe decreasekey operation is implemented by lowering the value at node and then percolating it up toward the root until heap order is established in the worst casethis can take (log ntimewhich is the length of the longest path toward the root in balanced tree this strategy does not work if the tree that represents the priority queue does not have (log ndepth as an exampleif this strategy is applied to leftist heapsthen the decreasekey operation could take (ntimeas the example in figure shows we see that for leftist heapsanother strategy is needed for the decreasekey operation our example will be the leftist heap in figure suppose we want to decrease the key with value down to if we make the changewe find that we have created violation of heap orderwhich is indicated by dashed line in figure the name comes from property of this data structurewhich we will prove later in the section