Fibonacci Heaps: Decrease Key Analysis
{"Image DocumentName": "Fibonacci Heaps: Decrease Key Analysis", "Image ImageDescription": "Actual cost. O(c) O(1) time for changing the key. O(1) time for each of c cuts, plus melding into root list. Change in potential. O(1) - c. trees(H ) = trees(H) + c. marks(H ) \uf0a3 marks(H) - c + 2. \uf044\uf046 \uf0a3 c + 2 \uf0d7 (-c + 2) = 4 - c. Amortized cost. O(1) \uf046(H) = trees(H) + 2 \uf0d7 marks(H) potential function. When marked node y is cut by cascading cut, its mark bit is cleared (2 units of potential). One unit pays for cut, the other for unit increase in potential due to y becoming a root. marks(H ) <= marks(H) - c + 2: each cut (except first) unmarks a node; last cut may or may not mark a node. Can scale units of potential to dominate cost hidden in O(c) term.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}