3

最小ヒープと最大ヒープの両方の機能を持つバイナリ ヒープ (優先キュー) を実装しようとしています。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) のままなので、これは機能する可能性があると思います。

4

4 に答える 4

4

簡単な方法は、M. Shaw が推奨するように、二分探索木を使用することです。

これをバイナリ ヒープの上に構築する必要がある場合は、各ヒープで、各要素と共に、要素の位置を他のヒープに格納します。1 つのヒープで要素を移動するたびに、他のヒープのその位置に直接移動して更新できます。delete-min または delete-max を実行する場合、他のヒープでコストのかかる線形スキャンは必要ありません。

たとえば、要素の値としてstd::pairs を他のヒープの位置として格納する場合、最小ヒープの 2 つの要素を交換し、最大ヒープの対応する要素を更新すると、次のようになります。firstsecond

swap(minheap[i], minheap[j]);
maxheap[minheap[i].second].second = i;
maxheap[minheap[j].second].second = j;
于 2015-07-23T03:18:01.353 に答える
0

http://www.geeksforgeeks.org/a-data-structure-question/

最も頻繁な操作がfindMinとfindMaxの場合、最小-最大ヒープは「user2357112」が指摘する答えです。完全に順序付けられたデータ構造が本当に必要ない場合、BST はやり過ぎかもしれません。上記は部分的に順序付けられたデータ構造です。上記のリンクを参照してください。

于 2015-07-24T09:19:38.593 に答える
0

あなたは近くにいます。秘訣は、別のレベルの間接化を使用することです。キーを配列 K[i] に保持し、インデックス i のみをヒープに格納します。また、2 つのリバース マップを保持します。1 つは最大ヒープ用で、もう 1 つは最小ヒープ用です。逆マップは、R[i] がキー K[i] のインデックス i の最小 (または最大) ヒープ内の場所であるような整数 R の配列です。つまり、M[j] が最小 (または最大) ヒープの場合、R[M[j]] = j; ヒープ内の要素を移動するためのふるい分け操作を行うときはいつでも、それぞれのリバース マップを同時に更新する必要があります。実際、上記の関係と同じように機能します。ヒープ要素 M[j] = z を変更するすべてのステップで、逆マップ R[z] = j も更新します。これにより、わずかな定数だけ実行時間が増加します。ヒープから K[i] を削除するには、一定の時間で見つけることができます: M[R[i]] にあります。

より大きなアルゴリズムの一部として実装したため、これが機能することを知っています（一定時間で削除するヒープオブジェクトを見つける）。https://github.com/gene-ressler/lulu/blob/master/ext/lulu/pq.cを確認してください。より大きなアルゴリズムは、マップ マーカーのマージ用です: https://github.com/gene-ressler/lulu/wiki

于 2015-07-23T03:34:32.783 に答える