配列対を使用したヒープ（ADT）の実装LinkedListの

私のデータ構造のコースでは、私は以下の時間でバイナリヒープを実装する必要がある - 複雑さの要件： - O（1）配列対を使用したヒープ（ADT）の実装LinkedListの

挿入 - O（LG n）で

はマックスを探します
マックス削除 - O（LG n）が

は、今は次のように配列を使用してこれを実現するために考えた：ヒープのルートは編曲である[1]（最初のインデックス）。 Arr [i]の子はArr [2i]とArr [2i + 1]（2人の子供）にあります。この実装では、O（1）でFind Maxを取得し、O（n）でMaxを削除し、例外でO（lg n）に挿入します。もし配列がいっぱいになったら挿入する必要があります。 O（log n）の代わりにO（n）となるように、O（n）のコストがかかります。

複雑な要件すべてに答える他の実装方法はありますか？私は配列の代わりにLinkedListを実装しようとしたかもしれないと思ったが、挿入はまだO（n）である。実装の提案は大歓迎です。

出典

2016-04-15 Noam

あなたの実装は要件を満たすことができます。私はあなたがdelete maxがO（n）を取ると言うとき、配列全体を1つの位置にシフトする必要があると考えていると思いますか？あなたが実際にそうする必要があるのは、彼らが言うように、一番大きな要素が「泳ぐ」という要素です。これにはO（lgn）時間が必要です。

また、サイズ変更が頻繁に行われないため、は、償却後の実行時間はまだO（lgn）です。 See here。

出典

2016-04-15 19:16:25

ありがとう、実際に私は "あなたが言及した技術を使用してO（ログn）"である "最大を削除する"と書くことを意味しています。私の問題はインサートです - 私は償却されたランタイムがO（ログn）であることを知っていますが、私は最悪の場合の実行時間がO（ログn）になる必要があります。しかし、別の方法で... – Noam

わかりました。そのウィキペディアの記事から得られた1つの考え*償却分析の動機付けは、1回の操作で最悪の場合の実行時間を見ても悲観的すぎる可能性があることです*。あなたは正しい実装をしていると思います。 [this powerpoint]（http://algs4.cs.princeton.edu/lectures/24PriorityQueues.pdf）を参照してください。現在の実装は依然としてO（lgn）とみなされます。 –

申し訳ございません。ですから、私はこのような実装をプローブで残しておきます。ありがとうございます – Noam

配列対を使用したヒープ（ADT）の実装LinkedListの

答えて

関連する問題