二項ヒープ パフォーマンス

ウィキペディア

二項ヒープ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/12 04:52 UTC 版)

パフォーマンス

n 個の要素を持つ二項ヒープに対して、以下の全操作の計算量はO(log n)である。

• ヒープに新しい要素を挿入する
• 最小のキーを持つ要素を検索する
• ヒープから最小のキーを持つ要素を削除する
• 指定された要素のキー値を減算する
• ヒープから特定の要素を削除する
• 二つの任意のヒープを一つのヒープにマージする

最小のキーを持つ要素の検索は、最小キーへのポインタを追加し利用することで、O(1)で実行できる。

派生

二項ヒープの派生は、フィボナッチヒープやソフトヒープのような他の似たようなヒープデータ構造を構築するのに用いられている。

関連項目

• ヒープ
• フィボナッチヒープ

外部リンク

• ウィキメディア・コモンズには、二項ヒープに関するカテゴリがあります。