問題タブ [binary-heap]

カスタムメイドのヒープ クラス関数を Priority Queue クラスで使用するのに本当に問題があります。PriorityQueue の "enqueue"、"dequeue"、"front"、および "size" 関数にヒープ クラスのどの関数を使用するかについて問題があります。「エンキュー」には挿入機能を使用する必要があることはわかっていますが、優先順位があるため、これを行う方法がわかりません。正しく機能するために、PriorityQueue クラスが Heap クラスの関数を使用するために必要なことを教えてもらえますか? 私はしばらくこれに固執しており、queue や heapq などの組み込みの Python 関数の使用を含む答えを見つけ続けています。

クラス ヒープ (オブジェクト):

これは機能していますが、以前に述べたように、これから優先キューを作成する方法に問題がありますか? コードを要求するのが間違っていることはわかっていますが、ここで誰か助けてもらえないかと切望しています。優先コードに何をさせたいかについての基本的な概要があります..

これは私がこれまでに得たものですが、完全に正しいかどうかはわかりません。誰か助けてくれませんか？

コードを編集して最新バージョンにしました。

最小ヒープと最大ヒープの両方の機能を持つバイナリ ヒープ (優先キュー) を実装しようとしています。insert(value)、extractMin()、およびextractMax()メソッドが必要です。抽出メソッドはヒープから値を削除し、値を返します。

minHeap私は元々とという 2 つの配列を使用していました。1maxHeapつはデータを最小ヒープ構造に格納するため、もう 1 つは同じデータを最大ヒープ構造に格納するためです。したがって、 を呼び出すとextractMin()、 から値が削除されて返されますminHeap。次に、両方のヒープでデータセットを同一に保つために、その値maxHeapも削除する必要があります (呼び出した場合はその逆)。extractMax()また、ヒープ順序プロパティにより、他のヒープの葉でその値を見つけることが保証されます。他のヒープでその値を検索すると、リーフのみを検索するため、O(n) またはより正確には O(n/2) の時間計算量になります。言うまでもなくpercolatingDown()、percolatingUp()値を削除した後にヒープを復元する方法は、すでに O(log n) です。したがって、合計で、抽出メソッドは O(n) になります。問題は、抽出メソッドを O(log n) にする必要があることです。

これについてもっと良い方法はありますか？

私もこのアイデアを考えましたが、最初に皆さんの考えを知りたいと思いました。

データの小さい半分を最大ヒープに、大きい半分を最小ヒープに配置することで、「中央ヒープ」のコーディングを終了しました。この構造により、特定の値セットの中央値を簡単に取得できます。そして、データの小さい半分を最小ヒープに配置し、大きい半分を最大ヒープに配置し、すべての値の平均 (中央値ではなく) を使用して、を呼び出すときに、値を最大ヒープまたは最小ヒープに配置しますinsert(value)。抽出メソッドは O(log n) のままなので、これは機能する可能性があると思います。

以下は私が行ったことですが、挿入時の最大要件を処理しません。

クラスに最大値を指定し、挿入でチェックしてから、最も重要でない要素を削除します。次に、実装で最も重要でない要素を特定します。

これを理解しようとするいくつかの問題があります。

皆さん、私はプログラミング クラスのラボ課題に取り組んでおり、ユーザーが配列に整数を入力して表示するヒープを作成する必要があります。最初の部分では、それらの同じ値を使用し、HeapSort をうまく使用することを想定しています。かなり簡単でしたが、このエラーが発生するたびに配列をソートするために HeapSort メソッドを呼び出そうとすると問題が発生します

スレッド「メイン」での例外 java.lang.NullPointerException
at HeapApp.heapSort(HeapApp.java:11)
at HeapApp.main(HeapApp.java:88)

エラーは具体的に指摘しています

と

助けてください！このクラスの最後の課題の 1 つです。

ヒープ クラス

を使用した Java の PriorityQueue コンストラクターの複雑さは何Collectionですか? 私はコンストラクタを使用しました：

複雑さは O(n) または O(n*log(n)) ですか?

Nノードと高さのバイナリ ヒープh:

最後の行: 最初の不等式は、 であることを意味しhますO(log N)。しかし、2 番目の 2 番目の不等式が であることを意味するのhはΩ(log N)なぜですか? それが「log2(N) < h」であれば理解できますが、私の問題は「1」の「h+1」にあります。

Speical minHeap は、各レベルが左から右にソートされる minHeap です。最悪の場合 、すべてのn要素を順番に印刷するにはどうすればよいですか?O(n)

minHeap は、ツリーが完全なバイナリ ツリーであるバイナリ ヒープによって実装されます (図を参照)。

特別な minHeap の例を次に示します。

したがって、結果は次のようになります。[1,3,4,5,8,10,17,18,20,22,25,30]

宿題からの質問。