二項ヒープ

二分ヒープではないことに注意 二分ヒープと比べて、マージが高速なことに特徴のあるデータ構造。 二分ヒープでは挿入が平均O(1)だが、特にマージのサポートはないため全体でO(N)になる 一方二項ヒープの場合はO(logN)である 代償として1要素の追加もマージを使うのでO(logN)掛かる…という記述を見かけたがこれも二分ヒープの挿入が平均定数時間なのと同じように平均O(1)だと思う

マージ、挿入、最小値検索、キー値減算、削除　O(logN) 最小値検索は追加の工夫によりO(1)にできる

二項ヒープ - Wikipedia