私が書いた方法で実装するのはとてつもない欠点があるのでしょうか?
ご自分のコメントでもう気付いておられるようですが、計算量の問題です。
(ついでに言うとLinked Listはデータ本体の他にリンクのための領域が必要になるので、その部分で避けたいと思う人があるかも知れませんが、この回答では触れません。)
挿入の計算量はlogH (Hは完全二分木の高さ)だ
この部分に書き間違いがあるので、余計混乱したのかも知れませんが、ヒープの挿入の計算量は、総ノード数n
に対して、(ワーストケースで)O(log n)
です。高さH
もlog n
で表されるので、混同されたのでしょうか。(この辺り全部単純二分ヒープを想定しています。)
挿入もO(n)でできて速い
前者のほうがlogHなので高さと要素数の兼ね合いでは速いかも
先述したようにO(n)
対O(log n)
です。Big-O記法を見慣れた人なら「O(log n)
の方がダントツに早い」なんて結論づけてしまうかも知れません。
n = 1000
程度の時、log_2 n ≒ 10
程度、いくら1回の操作がシンプルでも、1000回の繰り返しは、ほんのちょっと複雑な操作10回には負けるでしょうね。n
が大きくなれば、この差はますます大きくなります。
一方n = 30
程度の時にはどうなるでしょうか? log_2 n ≒ 5
となります。シンプルな操作30回とちょっと複雑な操作5回ではなかなか微妙なところです。n
が小さくなれば、この差はますます縮まります。
と言うわけで、
ヒープはデータの総量n
が多い時には極めて有効な方法
と言えるでしょう。
アルゴリズム・データ構造には状況・条件によって向き不向きがありますし、Big-O記法での計算量評価は、n
が小さい時にはあまりあてになりません。
ハッシュテーブル(辞書型とか言われることも多い)でのデータ1件取り出しはO(1)
と言うことになっているんですが、n = 10
程度なら配列を単純検索(O(n)
)の方が早くなることが多いです。
総数が最大でもn = 30
程度にしかならない状況で、(コードが理解しづらい)ヒープ処理を書こうとしている同僚を見つけたら、私なら「やめとけやりすぎや」と言って止めるでしょうね。自分で実装できるようになるべきかどうかは置いといて、条件・状況によって最適なアルゴリズム・データ構造を選べるようになりたいものです。
(私ならその程度の数なら、単純配列を用意して、挿入は場所探して配列ずらす、なんてことをするかもしれません。)