wake-up-neo.com

Wie finde ich den Mittelwert von Zahlen in linearer Zeit mithilfe von Haufen?

Wikipedia sagt: 

Auswahlalgorithmen: Ermitteln der min, max, sowohl min als auch max, median oder selbst das k-te größte Element kann .__ sein. in linearer Zeit mit Haufen durchgeführt.

Alles was es sagt ist, dass es getan werden kann und nicht wie.

Können Sie mir einen Anfang geben, wie dies mit Haufen möglich ist?

50
Lazer

Sie würden einen Min-Max-Median-Heap verwenden, um die Min-, Max- und Medianwerte in konstanter Zeit zu ermitteln (und lineare Zeit benötigen, um den Heap zu erstellen). Sie können Ordnungsstatistikbäume verwenden, um den k-ten kleinsten/größten Wert zu finden. Diese beiden Datenstrukturen sind in diesem Beitrag zu Min-Max-Heaps [pdf link] beschrieben. Min-Max-Heaps sind binäre Heaps, die zwischen Min-Heaps und Max-Heaps wechseln.

Aus dem Papier: Ein Min-Max-Median-Heap ist ein binärer Heap mit den folgenden Eigenschaften:

1) Der Median aller Elemente befindet sich an der Wurzel

2) Der linke Teilbaum der Wurzel ist ein min-max-Haufen H1 der Größengrenze [((n-1)/2)], der Elemente enthält, die kleiner oder gleich dem Median sind. Der rechte Teilbaum ist ein Max-Min-Heap Hr der Größe floor [((n-1)/2)], der nur Elemente enthält, die größer oder gleich dem Median sind.

In dem Artikel wird erklärt, wie man einen solchen Haufen baut.

Edit: Wenn Sie den Artikel gründlicher lesen, scheint es, als müssten Sie beim Aufbau der Min-Max-Median-Heaps zuerst den Median finden (FTA: "Finden Sie den Median aller n Elemente mit einem der bekannten linearen Zeitalgorithmen"). . Nachdem Sie den Heap erstellt haben, können Sie den Median beibehalten, indem Sie das Gleichgewicht zwischen dem Min-Max-Heap links und dem Max-Min-Heap rechts halten. DeleteMedian ersetzt die Wurzel entweder durch das Minimum des Max-Min-Heap oder das Maximum des Min-Max-Heap (je nachdem, welcher Wert das Gleichgewicht hält).

Wenn Sie also vorhaben, einen Min-Max-Median-Heap zu verwenden, um den Median eines festen Datensatzes zu ermitteln, sind Sie SOL. Wenn Sie ihn jedoch in einem sich ändernden Datensatz verwenden, ist dies möglich.

21
Niki Yoshiuchi

Siehe diese Wikipedia-Seite unter Auswahlalgorithmen . Schauen Sie sich insbesondere den BFPRT-Algorithmus und den Median of Medians-Algorithmus an. BFPRT ist wahrscheinlich linear und basiert auf Quicksort. Der Median des Medians ist garantiert linear, hat jedoch einen großen konstanten Faktor und kann daher in der Praxis länger dauern, abhängig von der Größe Ihres Datensatzes.

Wenn Sie nur ein paar hundert oder tausend Elemente zur Auswahl des Medians haben, vermute ich, dass ein einfacher Quicksort mit direkter Indexierung am einfachsten ist.

4
Dale Hagglund

Es gibt wahrscheinlich bessere Algorithmen da draußen, aber so würde ich es tun:

Habe zwei Eimer und einen Wert. Der Wert ist der Median, die beiden Eimer sind "größer als der Median" und "kleiner als der Median". Passen Sie für jedes Element x im Array die Buckets neu an, sodass sich big_bucket und small_bucket in ihrer Größe um höchstens 1 unterscheiden. Wenn Sie Elemente aus dem großen Eimer in den kleinen Eimer bewegen, müssen sie zuerst den Mittelwert durchlaufen, um dorthin zu gelangen (dh eine Differenz von 2 wird erfolgreich ein Element von einem Bucket zum nächsten schieben. Eine Differenz von 1 wird ein Element drücken von einem Bucket zum Medianwert.) Am Ende Ihres ersten Durchlaufs durch das Array sollte der Wert Ihr Median sein.

4
fbrereto

vielleicht war es nicht dabei, als die ursprüngliche Frage gestellt wurde, aber jetzt hat das Wiki einen Link zur Quelle und hier ist es: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091- 027.pdf

gehen Sie insbesondere auf Seite 17, und sehen Sie sich die Beschreibung von RSEL4 an. Sie beweisen in Satz 3.2, dass die zeitliche Komplexität dieses k-ten Auswahlalgorithmus O (k) ist. Sie brauchen also O(n), um den Haufen zu erstellen, und ein zusätzliches O(k), um den kleinsten k-ten Gegenstand zu finden.

es ist nicht wirklich so unkompliziert, wie andere Antworten vorgeschlagen haben

3
Shlomi

wenn Sie mehr über die Heap-Datenstruktur wissen, werden Sie leicht verstehen, dass dies tatsächlich der Fall ist. Eine Heap-Struktur kann in der Zeit O(n) erstellt werden, es gibt min Heap und Max Heap. Das minimale Heap-Wurzelelement gibt Ihnen das kleinste Element. Max Heap Root-Element gibt Ihnen das Max-Element. Nur beim Aufbau des Haufens finden Sie die min und max. Dieselbe Idee für den Median und den k-größten Wert. Während Sie Ihren Haufen erstellen, können Sie den Median und den k-größten Wert finden, indem Sie den linken oder rechten Zweig des Baums betrachten und eine konstante Menge an Speicherplatz für die Elementnummer beibehalten. usw.

0
DarthVader

Speichern Sie die erste Ganzzahl im Array und setzen Sie einen Zähler auf 1. Führen Sie dann die restlichen Ganzzahlen im Vektor durch. Wenn die aktuelle Ganzzahl im Array mit der gespeicherten Zahl identisch ist, wird der Zähler um eins erhöht, andernfalls wird der Zähler um eins verringert. Wenn der Zähler immer Null erreicht, verwerfen Sie die gespeicherte Ganzzahl und ersetzen Sie sie durch die aktuelle Ganzzahl im Array. Wenn Sie schließlich alle ganzen Zahlen durchlaufen haben, bleibt Ihnen ein Kandidat. Sie müssen dann das Array erneut durchlaufen und das Vorkommen des Kandidaten zählen, um sich zu vergewissern, dass dies wirklich ein Dominator ist. 

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;
}
0
jaycee