0

データ構造のヒープへの挿入方法で質問です。

ヒープへの挿入は、今あるノードの末尾に新しいノードを追加し、
その後、ヒープの条件を満たすような修正のオペレーションをすることだと
書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で見ました。
ネットでしらべても同様でした。
また挿入の計算量はlogH (Hは完全二分木の高さ)だとも見ました。

ここで疑問です。
そんなことをしなくても
ヒープ構造をlinked_listで作っておいて、挿入時は前から順番に走査し、
大小関係を満たすところにlinked_listの新しいノードとして挿入すればO(n)で挿入(nはノードの個数)できます。
この方法のほうがシンプルですし、挿入もO(n)でできて速いのかなと思います。
まぁ、前者のほうがlogHなので高さと要素数の兼ね合いでは速いかもですね。

ただ、前述に述べた方法をみんな説明していたのでそれがスタンダートかつベストプラクティスなんだろうなと思っています。

私が書いた方法で実装するのはとてつもない欠点があるのでしょうか?

1
  • あれ、自分で書いててあとで気がつきましたが、O(n) より O(logn)のほうが速いので速くなるシチュエーションがなさそうな気が、、、 Commented 2019年6月1日 1:36

1 件の回答 1

3

私が書いた方法で実装するのはとてつもない欠点があるのでしょうか?

ご自分のコメントでもう気付いておられるようですが、計算量の問題です。

(ついでに言うとLinked Listはデータ本体の他にリンクのための領域が必要になるので、その部分で避けたいと思う人があるかも知れませんが、この回答では触れません。)

挿入の計算量はlogH (Hは完全二分木の高さ)だ

この部分に書き間違いがあるので、余計混乱したのかも知れませんが、ヒープの挿入の計算量は、総ノード数nに対して、(ワーストケースで)O(log n)です。高さHlog 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程度にしかならない状況で、(コードが理解しづらい)ヒープ処理を書こうとしている同僚を見つけたら、私なら「やめとけやりすぎや」と言って止めるでしょうね。自分で実装できるようになるべきかどうかは置いといて、条件・状況によって最適なアルゴリズム・データ構造を選べるようになりたいものです。

(私ならその程度の数なら、単純配列を用意して、挿入は場所探して配列ずらす、なんてことをするかもしれません。)

1
  • ものすごく親切に説明くださりありがとうございます!使い所に関してもよく理解できました! Commented 2019年6月1日 7:40

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。