pairing-heap

0熱

1答えて

私は自分のコースの課題に取り組んでいますが、1つの質問ではペアリングヒープのキーを減らす操作にO（1）時間がかかることを示しています。明らかに、減少させたいキーへのポインタがあれば、操作はO（1）時間かかる（リンクを削除し、キー値を変更してからマージする）。ただし、割り当てのどこにキーへのポインタが指定されているとは言えません。もしポインタが与えられていなければ、reduceキーはO（1）時間