最小値検索

ウィキペディア小見出し辞書

最小値検索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/05 08:19 UTC 版)

「二項ヒープ」の記事における「最小値検索」の解説

ヒープの最小要素を見つけるには、ただ二項木たちの根の中で最小のものを見つけるだけでよい。この処理は O(log n)時間内にたやすく完了できる。 最小要素を含む二項木を指すポインタを使うことによって、この操作にかかる時間をO(1)にまで減らすことができる。そのポインタは最小要素検索以外の任意の操作を行うときにおいても必ず更新しなければならない。この操作は、任意の操作を行う時間とは別にO(log n)時間内に完了する。