フィボナッチヒープ
柔軟な構造を持つために、一部の操作には長い時間がかかる一方、他の操作は非常に速く終わるということが起きる。走行時間の償却解析においては、「非常に速い操作」の所要時間は実際の所要時間よりも若干長いものとして扱う。この余分な時間は、後に「遅い操作」が実際に要した時間から差し引かれる。後で使うために取っておかれている時間の量は、任意の時点でポテンシャル関数によって計測される。フィボナッチヒープのポテンシャル関数は次式によって与えられる。
P o t e n t i a l = t + 2 m {\displaystyle Potential=t+2m}
ここで t はフィボナッチヒープの中にある木の数、m はマークされたノードの数である。あるノードは、自身が他のノードの子となって以降、自身の子が少なくとも一つ切り取られたならばマークされる(但しルートはマークせず、マークされたノードがルートになった場合はマークを消す)。
従って、ヒープ内のそれぞれの木のルートは 1 単位時間を保持している。この単位時間は後でこの木を他の木と償却時間 0 でリンクするのに使うことができる。また、個々のマークされたノードは 2 単位時間を保持している。このうち 1 単位時間はそのノードを親から切り離すのに使うことができる。もしこれが起きると、そのノードはルートとなり、残る 2 つめの単位時間を他のルートと同様に保持し続けることになる。