2

私は最近、すでに書かれているいくつかのコードでプロジェクトを開始しました。彼の実装を調べることにしたところ、彼が単一リンク リストを使用してプライオリティ キューを実装していることがわかりました。

SLL についての私の理解では、リスト全体を反復処理する必要がある場合があるため、そのように実装するのは非効率的です。そのため、ヒープが好まれます。しかし、おそらく私はその背後にある何らかの理由を見逃しており、優先度キューにヒープではなく SLL を選択したことがある人がいるかどうか疑問に思っていましたか?

4

2 に答える 2

0

プライオリティ キューを実装するには、ヒープよりも SLL の方が適している場合があります。例えば：

  1. キューから削除するときは、できるだけ速くする必要があります。SLL からの削除は O(1) (リスト/キューの先頭から) ですが、ヒープからの削除は O(log n) です。alarm()シンプルなOS用のシステムコールのバージョンを書いているときに、実際にこれに遭遇しました。O(log n) ルックアップ時間を費やす余裕がありませんでした。これに関連して、一度に複数の要素を削除する必要がある場合があります。SLL から k 要素を削除するには O(k) 時間がかかりますが、ヒープには O(k log n) 時間がかかります。
  2. メモリの問題。最小ヒープまたは最大ヒープの従来の実装には配列が含まれており、ヒープが大きくなるにつれてサイズを変更する必要があります。大規模な作業を行うのに時間がかかる余裕がない場合はrealloc、この戦略は終わりです。ヒープをバイナリ ツリーとして実装する場合は、SLL 用に 1 つではなく 2 つのポインターが必要です。
  3. 複数の優先順位を維持する必要がある場合。異なるリンク リスト内の同じノードを追跡するのは比較的簡単です。ヒープでこれを行うのは、はるかに複雑です。
于 2011-06-20T18:25:14.480 に答える
-1

大学では、Linked List を使用する唯一の理由は、ポインタの理解を助けるためだと言われた.

于 2011-06-20T16:52:03.560 に答える