問題タブ [heap]

バイナリ ヒープに浸透する子ノードを選択する際の最適化はありますか? たとえば、最小ヒープで、親ノードが 10 で、その子ノードが 8 と 3 の場合、どのノードと交換するのがよいでしょうか?

より大きな子ノードとスワップすることを選択すると、それより下の子ノードが 8 よりも大きくなるため、停止する可能性が高くなるように思われます。これに関する調査はありますか?

基本的に、データストレージとして sqlite を使用した最小ヒープ機能が必要です。
2列のテーブルが必要だとしましょう。1 番目は一意の ID で、
2 番目は整数値です。
最小の整数値を持つ ID が常に必要です。

助言がありますか ？？

ヒープを使用する必要があるプログラムを作成していますが、ソート方法以外はすべて正常に動作します。明らかに非常に重要です! 私の論理の何が問題なのか、それともばかげた何かが欠けているのかわかりません。しかし、これを見て新鮮な目を向けるといいでしょう。

関数には、もちろんヒープ、ルートの場所である私のベクトルが渡され、述語として STL レスまたはグレーターのいずれかが渡されます。

何が間違っているのですか？

重複の可能性：
Pythonのヒープにキーを減らす機能を実装するにはどうすればよいですか？

やあ、

Pythonでheapqを使用して、優先キューを実装しています。キュー内のアイテムの優先順位は大幅に変更されます。その場合は、ヒープをヒープ化する必要があります。
問題は、heapqにはヒープ全体をヒープ化するheapify関数しかなく、ヒープ内の特定のアイテムから開始するheapifyがあり、残りはすでに適切に順序付けられたヒープであることを認識していることです（従来のCS教科書heapifyのように）。
各heapify呼び出しはO（lgn）ではなくO（n）であるため、違いは重要です。標準リストを使用してヒープを実装せずに実行できますか？

ありがとう！

私の質問は、Pythonのヒープにキーを減らす機能を実装するにはどうすればよいですか？
そこでの答えは、特定のアイテムの適切なO（lgn）ヒープ化を使用して、ヒープベースのキューを再実装する方法がないことを示しています。

しばらく前に、d-ary max-heap (各ノードが最大 d 個の子を持つヒープ) を使用して n 個の数値の配列をソートする ac プログラムを作成する割り当てが与えられました。プログラムは、2 から配列のサイズまでの値である d の値を入力するようユーザーに要求する必要がありました。プログラムをチェックしているときに、誤って d の値として 1 を入力してしまい、アルゴリズムが 1-ary ヒープを使用して配列を正しくソートすることに成功しましたが、d の通常の値よりも多くの時間がかかりました。

そんなことがあるものか？1-ary ヒープは単なるリストのようなヒープではなく、すべてのノードには 1 つの子しかありません。この並べ替えがどのように発生するかを説明できる人はいますか?

私の質問は次のとおりです。

トリプルのリストが与えられ、それらは hash_heap と呼ばれるデータ構造に格納されます (名前についてはわかりませんが、ハッシュテーブルとヒープが混在している必要があります)。そして、データ構造が次のメソッドを提供することを願っています。

このようなデータ構造を実装することは可能ですか? ハッシュテーブルが最初の方法をサポートし、ヒープが 2 番目と 3 番目の方法をサポートできることは知っていますが、それらを組み合わせる方法がわかりません。何か案は？

ありがとう！

配列にデータを格納している MinMax Heap の実装がたくさん見つかりました。それは私が何か違うものを探している方法です。左の子と右の子へのポインター (および比較するキー) を持つヒープの要素のみを使用して、MinMax ヒープを作成したいと考えています。したがって、ヒープにはルート オブジェクト (最小レベル) へのポインターのみがあり、ルート オブジェクトにはその子へのポインター (最大レベル) などがあります。新しいオブジェクトを挿入する方法は知っていますが (ヒープ サイズに応じて int のバイナリ表現を使用して適切なパスを見つける)、残りを実装する方法はわかりません (要素を押し上げ (押し下げ)、親または祖父母を見つけます)。 .

助けてくれてありがとう

全体像としては、プライオリティ キューを使用してダイクストラのアルゴリズムを実装しようとしています。

golang-nuts のメンバーによると、Go でこれを行う慣用的な方法は、カスタムの基礎となるデータ構造でヒープ インターフェイスを使用することです。だから私は Node.go と PQueue.go を次のように作成しました:

そして PQueue.go:

main.go: (アクションは SolveMatrix にあります)

問題は、コンパイル時にエラーメッセージが表示されることです。

そして、行 PQ.Push(firstNode) をコメントアウトすると、コンパイラーは満足します。しかし、そもそもエラー メッセージが表示される理由がわかりません。Push は引数を変更しません。

更新: 将来の検索でこれに遭遇する人のために、上記のコードには大きな誤解がぎっしり詰まっています。より便利なテンプレートについては、以下をご覧ください: Node.go:

PQueue.go:

次のコードがあるとします。

戻り値が次のようになる理由:

sort_heap(v.begin(), v.end(), Greater) を呼び出すと、戻り値は30 20 15 10 9.

質問 > このサンプルでは、​​最小ヒープを作成します。これが sort_heap(v.begin(), v.end()) を呼び出せない理由ですか?

ありがとうございました

インタビューの質問:

以下で編集 配列が与えられます。そこから 2 つのヒープを作成します。1 つは最小ヒープ、もう 1 つは最大ヒープです。これら 2 つの提供されたヒープを使用して、O(nlog n) 時間で配列の中央値を見つけます。

修正された質問 番号はランダムに生成され、(拡張) 配列に格納されます。中央値をどのように追跡しますか？

解決策 この問題は 2 つのヒープを使用して解決でき、中央値は常に O(1) 時間でアクセスできます。