ペアリングヒープ - キーを減らすためのO（1）？

Question

私は自分のコースの課題に取り組んでいますが、1つの質問ではペアリングヒープのキーを減らす操作にO（1）時間がかかることを示しています。

明らかに、減少させたいキーへのポインタがあれば、操作はO（1）時間かかる（リンクを削除し、キー値を変更してからマージする）。

ただし、割り当てのどこにキーへのポインタが指定されているとは言えません。もしポインタが与えられていなければ、reduceキーはO（1）時間かかるでしょう（最初にヒープ内のキーを探す必要がありますが、これは一定の時間がかかりません）。私は文学を見て、すべてが減少キーがO（logn）時間かかると言う。

ここに何か不足していますか？

Answer 1

ペアリングヒープの減少キーの償却コストは、問題の要素へのポインタを持っていてもO（1）ではありません。ペアリングヒープのキー減少操作の償却コストには、Ω（ログログn）の下限があることが証明されています。これは証明するのは容易ではありません。詳細はthis paperを参照してください。