問題タブ [minmax-heap]

O(1)最小値と最大値をのぞき見し、の要素を削除できるヒープである、最小-最大ヒープの信頼性の高いJava実装を備えた人気のあるライブラリ（Apache、Googleなどのコレクション）を知っていますO(log n)か？

私は最小-最大ヒープを実装しています。これは両端のプライオリティ キューの一種です。min-max ヒープの詳細については、こちらを参照してください。

挿入操作と最小削除操作のコードは単純で、ネット上で入手できます。しかし、 min-max ヒープにdelete-max操作を実装しようとしています。

最初は、min-max ヒープの delete-max は max-min ヒープの delete-max と同じだろうと感じました (最大の要素を含む min-max ヒープのサブツリーを考えると、max-min ヒープに似ています)。したがって、実装はシンプルで、min-max ヒープの delete-min に似ています。

しかし問題がある：

上の図からわかるように、最大​​要素は 70 ですが、min-max ヒープの最後の要素 (12)は、70 を含むサブツリーにはありません。したがって、それを使用して、左のサブツリーに残されたギャップを置き換えることができますか? 70の削除後？

その要素を使用せず、代わりに max-min ヒープの delete-max 手順に従い、20 を使用してギャップを置き換えると、ヒープに挿入される次の要素は 10 の右の子になり、右の子は永久になくなります。 9の。

それで、誰かが私を助けることができますか？

min-max heap、つまり、最小値と最大値を見つけることが一定の操作であるヒープを作成しました。クラスのテストを作成したいので、ヒープが最小最大ヒープかどうかをチェックする関数を実装することにしました。ここにありますが、100% 正しいかどうかはわかりません。

このヒープの要素は class で表されることに注意してください。そのため、そのクラスのオブジェクトのみが含まれているHeapNodeかどうかを確認しています。self.heap偶数レベルは、たとえば 0、2、4 などです。このヒープの最小値は にありますself.heap[0]。最大値はmax(self.heap[1], self.heap[2])(両方が存在する場合) です。ノードの祖父母が存在しない場合にh.grandparent_index(i)返します。Nonei

私のアルゴリズムのアイデアはとてもシンプルです。下から始めて、奇数レベルの偶数かどうかを確認します。偶数レベルの場合、要素がその祖父母よりも大きいことを確認する必要があります。私が奇妙なレベルにいる場合は、祖父母よりも小さいことを確認する必要があります.

私のアルゴリズムは正しいですか？私はいくつかのポイントを逃していますか？それが正しければ、それを改善するための提案は十分に受け入れられます。

最終的に、私の実装は他の誰かにとって役立つかもしれません。

編集 1

私の関数は、偶数 (およびそれぞれ奇数) レベルの要素が互いに正しく配置されているかどうかをチェックしますが、最大要素が または で見つかったかどうか、self.heap[1]およびself.heap[2]最小要素が であるかどうかはチェックしないことに気付きましたself.heap[0]。

編集 2

編集1と@goCardsの回答に従って、新しい更新されたコードを追加しています。

値に基づいてハッシュマップをソートしたいとします。これを行うには、コンパレータを使用して priorityQueue を実装します。その結果、結果の pq は、インデックス 0 から最後まで、最大から最小へと並べ替えられます。

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

しかし、誰かがそれは maxheap だと言いました。ヒープは単に親の値が子の値よりも大きいことは理解していますが、なぜ maxheap なのか理解できませんか? コンパレーターをpriorityQueueに実装しているだけですか？これはヒープとどのように関係していますか?

find-min最小-最大ヒープは、時間とfind-max操作が一定であるため、両端優先キューを実装するのに役立ちます。O(log ₂ n)時間で min-max ヒープの最小要素と最大要素を取得することもできます。ただし、場合によっては、min-max ヒープ内の任意のノードを削除することもできます。これは、min-max heaps を紹介した論文によると、O(log ₂ n)で実行できます。

...

構造体は、任意の固定値 (または値のセット) に対して、定数時間での操作 (構造体でk 番目Find(k)に小さい値を決定する) と対数時間での操作 (構造体で k 番目に小さい値を削除する)をサポートするように一般化することもできます。の。Delete(k)k

...

min-max ヒープで k 番目の要素を削除するにはどうすればよいですか?