問題タブ [heap]

私は試験の準備で忙しく、古い試験問題をやっているだけです。以下の質問は、私ができないように見える唯一のものです (どこから始めればよいかわかりません)。どんな助けでも大歓迎です。

Ω(nlogn) 比較ソート境界、ボトムアップ ヒープ構築の theta(n) 境界、および挿入ソートの順序複雑度を使用して、ヒープ内の反転の最悪のケースの数が Ω(nlogn) であることを示します。

私は最小ヒープと最大ヒープを研究しましたが、いくつか質問があります。

1. ソートされた配列は最小ヒープですか？
2. 最大ヒープの最小値はいくつですか？

ヒープデータ構造では、左の子がそれ自体のレベルで右の子よりも多くなる可能性があるというこの質問がありますか？つまり、これらの3つの数値9、5、8を考慮して、ルートが9になるように最大ヒープのデータ構造を作成したいのですが、8が左の子で、5が右の子であるというのは本当ですか？助けてくださいありがとう

これは私のデータ構造の本の例であり、この演習では、これは最大ヒープではないと書かれていますが、その理由が最大ヒープではない理由を教えてください。

iterable の n 番目に大きい項目の元のリストのインデックスを返すにはどうすればよいですか

これにはすでに数時間かかりました。私はそれを理解することはできません。

Perl で Heap::Simple インターフェースに二次順序付けを定義するにはどうすればよいですか?

なぜヒープの概念がコンテナーではなくアルゴリズム( make_heap、pop_heap、 ) として実装されているのか疑問に思っていました。私が特に興味を持っているのは、一部のソリューションが理由を説明でき、同様のアルゴリズムのコレクション (make_set add_set rm_set など) の代わりにコンテナーであるということです。push_heapsort_heapsetmap

私はこれを何時間も見ていて、これを理解することはできません。heapify関数の比較がより大きい値に変更された場合、出力は本来あるべき昇順になります。リストを降順で並べ替えたいのですが、次のコードを使用しても正しい出力が得られません。

プログラム出力：

以前は、要素エントリをただの配列として定義していましHeap::Simpleた。これは、2 番目の並べ替えが必要なかったからです。

作成したヒープに配列参照を挿入するための要素を定義するためのセカンダリ ソートと関数を実装した後、挿入の実行時間が (かなり!) 増加しました。Heap::Simpleこれについては、以下のドキュメントで説明されています。Any

ただし、Any要素タイプを使用することの欠点を理解するのに苦労しています。追加の配列参照を作成する予定はありますか? key_insert実行時間を短縮するために使用する必要がありますか?

現在のコードは次のとおりです。

コンテキスト: Perl ヒープへの配列参照の挿入

Perl で Heap::Simple に挿入するときに、誰かがセカンダリ キーを使用したことがあるかどうかを調査したかったのですか? もしそうなら、あなたのパフォーマンスはこれまでに影響を受けましたか?