52

ウィキペディアは次のように述べています。

選択アルゴリズム: ヒープを使用して、最小値、最大値、最小値と最大値の両方、中央値、さらには k 番目に大きい要素を見つけることを線形時間で行うことができます。

それが言っているのは、それができるということだけであり、方法ではありません。

ヒープを使用してこれを行う方法を教えてください。

4

7 に答える 7

21

min-max-median ヒープを使用して、最小値、最大値、および中央値を一定時間で見つけます (ヒープの構築には線形時間がかかります)。順序統計ツリーを使用して、k 番目に小さい/大きい値を見つけることができます。これらのデータ構造は両方とも、最小-最大ヒープ [PDF] に関するこの論文で説明されています。最小-最大ヒープは、最小ヒープと最大ヒープを交互に繰り返すバイナリ ヒープです。

紙から：

min-max-median ヒープは、次のプロパティを持つバイナリ ツリーです。

  1. すべての要素の中央値はルートにあります

  2. ルートの左側のサブツリーは、中央値以下の要素を含むサイズceiling[((n-1)/2)]の最小-最大ヒープHlです。右側のサブツリーは、サイズが floor[((n-1)/2)] の最大最小ヒープ Hr で、中央値以上の要素のみが含まれています。

この論文は、そのようなヒープを構築する方法を説明しています。

この論文をより詳しく読むと、最小-最大-中央値ヒープを構築するには、最初に中央値を見つける必要があるように見えます(FTA: 「既知の線形時間アルゴリズムのいずれかを使用して、すべての n 要素の中央値を見つける」)。つまり、ヒープを構築したら、左側の最小 - 最大ヒープと右側の最大 - 最小ヒープのバランスを維持するだけで中央値を維持できます。DeleteMedian は、ルートを max-min ヒープの最小値または min-max ヒープの最大値 (バランスを維持する方) に置き換えます。

したがって、min-max-median ヒープを使用して固定データ セットの中央値を見つけることを計画している場合は SOL ですが、変化するデータ セットで使用している場合は可能です。

于 2010-04-09T23:34:46.310 に答える
4

選択アルゴリズムに関するこのウィキペディアのページを参照してください。特に、BFPRT アルゴリズムと Median of Medians アルゴリズムを見てください。BFPRT は確率的に線形であり、クイックソートをモデルにしています。中央値の中央値は線形であることが保証されていますが、定数係数が大きいため、データセットのサイズによっては、実際には時間がかかる場合があります。

中央値を選択する要素が数百または数千しかない場合は、単純なクイックソートとそれに続く直接インデックス付けが最も簡単だと思います。

于 2010-04-05T18:08:17.623 に答える
4

より優れたアルゴリズムが存在する可能性がありますが、私がそれを行う方法は次のとおりです。

2 つのバケットと 1 つの値があります。値は中央値で、2 つのバケットは「中央値よりも大きい」と「中央値よりも小さい」です。配列内の各要素について、とのサイズの差が 1 以下になるxようにバケットを再調整します。大きなバケツから小さなバケツにアイテムを移動する場合、そこに到達するにはまず中央値を通過する必要があります (つまり、2 の差があると、あるバケットから次のバケツに要素が正常にプッシュされます。1 の差があると、要素がプッシュされます)。 1 つのバケットから中央値まで。) 配列を最初に通過した時点で、値は中央値になるはずです。big_bucketsmall_bucket

于 2010-04-05T18:08:44.487 に答える
3

元の質問が出されたときはおそらくそうではありませんでしたが、現在wikiにはソースへのリンクがあり、ここにあります：http: //ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091 -027.pdf

具体的には、17ページに移動し、 RSEL4の説明を確認してください。彼らは定理3.2で、このk番目の選択アルゴリズムの時間計算量がO（k）であることを証明しています。したがって、ヒープを構築するにはO（n）が必要であり、k番目に小さいアイテムを見つけるには追加のO（k）が必要です。

他のいくつかの回答が示唆しているほど簡単ではありません。

于 2012-02-15T00:36:56.720 に答える
1

最初の整数を配列に格納し、カウンターを 1 に設定します。次に、ベクトル内の残りの整数をループします。配列内の現在の整数が格納されている整数と同じ場合、カウンターは 1 増加し、そうでない場合は 1 減少します。カウンターがゼロになった場合は、格納されている整数を破棄し、配列内の現在の整数に置き換えます。最終的にすべての整数をループすると、1 つの候補が残ります。次に、配列を再度ループし、候補の出現回数を数えて、これが実際にドミネーターであることを確認する必要があります。

static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
   if(arr[i] == candidate) counter++
    else 
   {
        counter--;
        if(counter == 0) { candidate = arr[i]; counter = 1; }
    }
}
counter = 0;
for(int i = 0;  i < n; i++)
{
    if(arr[i] == candidate) counter++;
}
if(counter > n / 2) return candidate;
else return -1;
}
于 2015-03-26T17:34:17.980 に答える
0

ヒープのデータ構造について詳しく知っていれば、実際にそうであることが容易に理解できます。ヒープ構造は O(n) 時間で構築できます。最小ヒープと最大ヒープがあります。min heap root element は、最小の要素を提供します。max heap root element は最大要素を提供します。ヒープを構築するだけで、最小値と最大値がわかります。中央値と k 番目の最大値についても同じ考えですが、ヒープを構築しているときに、ツリーの左または右の枝を見て、要素番号を格納するための一定量のメモリを保持することで、中央値と k 番目の最大値を見つけることができます。等

于 2010-04-08T03:32:37.313 に答える
-1

明らかに、O(n) の最小値と最大値は簡単で、ヒープは必要ありません。

K 番目に大きい値は、これまでの上位 k 値の k サイズのヒープを維持することでかなり簡単に実行できます。ランタイムは O(n*logk) になります。k が固定サイズで k << n の場合、その線形時間と呼ぶことができます。

中央値はありえないと思います。O(n) サイズのヒープを作成するだけでも、O(n*logn) 時間が必要です。

編集: わかりました、これについてもう少し考えた後、IVlad は正しいです。固定サイズの O(n) でヒープを作成できます。しかし...それはOPの中央値の質問には役立ちません。線形ヒープ作成手法では、最終出力として有効なヒープのみが生成されます。n 回の挿入を行う単純なアプローチでは、各ステップの後に有効なヒープが O(n*logn) になります。

ヒープを使用して中央値を見つけるには、実行中のサブヒープを使用する必要があるように思えます。たとえば、この問題のアルゴリズムを提案するブログ投稿にリンクされている回答がここに投稿されました (現在は削除されているようです)。データを 1 回通過するため、2 つのヒープ (小さい方の半分と大きい方の半分) を使用して実行中の中央値を追跡しました。それには、ヒープの挿入および削除時に有効なヒープを維持することに依存するため、より遅く単純なヒープ アプローチが必要になります。

線形のワンショット ヒープ作成手法を使用して中央値を見つける他の方法はありますか?

于 2010-04-05T18:12:15.530 に答える