Holen Sie sich 100 höchste Zahlen aus einer unendlichen Liste

53

Einer meiner Freunde wurde diese Interviewfrage gestellt -

"Es gibt einen konstanten Zahlenfluss aus einer unendlichen Liste von Zahlen, aus der Sie eine Datenstruktur erstellen müssen, um die 100 höchsten Zahlen zu einem bestimmten Zeitpunkt zurückzugeben. Angenommen, alle Zahlen sind nur ganze Zahlen."

Dies ist ganz einfach. Sie müssen eine sortierte Liste in absteigender Reihenfolge und einen Titel mit der niedrigsten Nummer in dieser Liste führen. Wenn die neu erhaltene Nummer größer als die niedrigste ist, müssen Sie diese niedrigste Nummer entfernen und die neue Nummer nach Bedarf in die sortierte Liste einfügen.

Dann wurde die Frage erweitert -

"Können Sie sicherstellen, dass die Reihenfolge für die Einfügung O (1) sein sollte? Ist es möglich?"

Selbst wenn Sie eine neue Nummer hinzufügen, um sie aufzulisten und mit einem beliebigen Sortieralgorithmus erneut zu sortieren, ist dies meines Wissens nach am besten O (logn) für Quicksort (glaube ich). Also mein Freund sagte, es sei nicht möglich. Aber er war nicht überzeugt, er bat darum, eine andere Datenstruktur als eine Liste beizubehalten.

Ich dachte an einen ausgeglichenen Binärbaum, aber selbst dort werden Sie die Einfügung mit der Reihenfolge 1 nicht erhalten. Also die gleiche Frage habe ich jetzt auch. Wollte wissen, ob es eine solche Datenstruktur gibt, die das Einfügen in der Reihenfolge 1 für das obige Problem ausführen kann, oder ob dies überhaupt nicht möglich ist.

Sachin Shanbhag
quelle
19
Vielleicht verstehe ich die Frage nur falsch, aber warum müssen Sie eine sortierte Liste führen? Warum nicht einfach den Überblick über die niedrigste Nummer behalten und wenn eine höhere Nummer als diese angetroffen wird, die niedrigste Nummer entfernen und die neue Nummer eingeben, ohne die Liste zu sortieren? Das würde dir O (1) geben.
EdoDodo
36
@EdoDodo - und woher wissen Sie nach dieser Operation, was die neue niedrigste Zahl ist?
Damien_The_Unbeliever
19
Sortieren Sie die Liste [O (100 * log (100)) = O (1)] oder durchsuchen Sie sie linear nach dem Minimum [O (100) = O (1)], um die neue niedrigste Zahl zu erhalten. Ihre Liste hat eine konstante Größe, daher sind alle diese Vorgänge auch zeitlich konstant.
Random832
6
Sie müssen nicht die gesamte Liste sortiert halten. Es ist dir egal, was die höchste oder zweithöchste Zahl ist. Sie müssen nur wissen, was der niedrigste ist. Nachdem Sie eine neue Zahl eingegeben haben, durchlaufen Sie einfach die 100 Zahlen und sehen, welche jetzt am niedrigsten ist. Das ist konstante Zeit.
Tom Zych
27
Die asymptotische Reihenfolge einer Operation ist nur dann interessant, wenn die Größe des Problems unbegrenzt anwachsen kann. Aus Ihrer Frage ist sehr unklar, welche Menge ungebunden wächst; Es hört sich so an, als würden Sie fragen, wie die asymptotische Reihenfolge für ein Problem ist, dessen Größe auf 100 begrenzt ist. das ist nicht einmal eine vernünftige Frage; Etwas muss ohne Grenzen wachsen. Wenn die Frage lautet: "Können Sie es tun, um die Top n, nicht die Top 100, in O (1) -Zeit zu behalten?" dann ist die frage sinnvoll.
Eric Lippert

Antworten:

35

Angenommen, k ist die Anzahl der höchsten Zahlen, die Sie kennen möchten (100 in Ihrem Beispiel). Dann können Sie eine neue Nummer hinzufügen, in O(k)der auch steht O(1). Weil O(k*g) = O(g) if k is not zero and constant.

duedl0r
quelle
6
O (50) ist O (n), nicht O (1). Das Einfügen in eine Liste der Länge N in O (1) bedeutet, dass die Zeit nicht vom Wert N abhängt. Das heißt, wenn 100 zu 10000 wird, darf 50 NICHT zu 5000 werden.
18
@hamstergene - aber bei dieser Frage ist Ndie Größe der sortierten Liste oder die Anzahl der Elemente, die bisher verarbeitet wurden? Wenn Sie 10000 Elemente verarbeiten und die ersten 100 Elemente in einer Liste beibehalten oder 1000000000 Elemente verarbeiten und die ersten 100 Elemente in einer sortierten Liste beibehalten, bleiben die Einfügungskosten in dieser Liste gleich.
Damien_The_Unbeliever
6
@hamstergene: In diesem Fall hast du die Grundlagen falsch verstanden. In Ihrem Wikipedia - Link gibt es eine Eigenschaft ( „Multiplikation mit einer Konstanten“): O(k*g) = O(g) if k not zero and constant. => O(50*1) = O(1).
duedl0r
9
Ich denke duedl0r hat recht. Lassen Sie uns das Problem reduzieren und sagen, dass Sie nur die Minimal- und Maximalwerte benötigen. Ist dies O (n), weil das Minimum und das Maximum 2 sind? (n = 2). Nr. 2 ist Teil der Problemdefinition. Ist eine Konstante, so ist es in der O (k * etwas), die O (etwas) entspricht
Xanatos
9
@hamstergene: über welche funktion sprichst du? Der Wert 100 scheint mir ziemlich konstant zu sein.
duedl0r
19

Halten Sie die Liste unsortiert. Das Herausfinden, ob eine neue Nummer eingefügt werden soll, dauert länger, aber das Einfügen ist O (1).

Emilio M Bumachar
quelle
7
Ich denke, das würde dir den Smart-Aleck Award bringen, wenn sonst nichts. * 8 ')
Mark Booth
4
@Emilio, du bist technisch korrekt - und das ist natürlich die beste Art von richtig…
Gareth
1
Sie können aber auch die niedrigste Ihrer 100 Zahlen behalten, dann können Sie auch entscheiden, ob Sie in O (1) einfügen müssen. Erst wenn Sie eine Nummer eingeben, müssen Sie die neue niedrigste Nummer suchen. Dies geschieht jedoch seltener, als sich für das Einfügen zu entscheiden oder nicht, was bei jeder neuen Nummer der Fall ist.
Andrei Vajna II
12

Das ist einfach. Die Größe der Liste der Konstanten, also die Sortierzeit der Liste, ist konstant. Eine Operation, die in konstanter Zeit ausgeführt wird, wird als O (1) bezeichnet. Daher ist das Sortieren der Liste für eine Liste mit fester Größe O (1).

Kirk Broadhurst
quelle
9

Sobald Sie 100 Nummern übergeben haben, sind die maximalen Kosten für die nächste Nummer die Kosten für die Überprüfung, ob die Nummer unter den höchsten 100 Nummern liegt (nennen wir diese CheckTime ), zuzüglich der Kosten für die Eingabe in diesen Satz und das Auswerfen der niedrigste (nennen wir diese EnterTime ), die konstante Zeit ist (zumindest für begrenzte Zahlen), oder O (1) .

Worst = CheckTime + EnterTime

Wenn die Verteilung der Zahlen zufällig ist, sinken die durchschnittlichen Kosten, je mehr Zahlen Sie haben. Beispielsweise ist die Wahrscheinlichkeit, dass Sie die 101. Zahl in die maximale Menge eingeben müssen, 100/101, die Wahrscheinlichkeit für die 1000. Zahl wäre 1/10 und die Wahrscheinlichkeit für die n-te Zahl wäre 100 / n. Daher lautet unsere Gleichung für die durchschnittlichen Kosten:

Average = CheckTime + EnterTime / n

Daher ist, wenn n gegen unendlich geht, nur CheckTime wichtig:

Average = CheckTime

Wenn die Zahlen gebunden sind, ist CheckTime konstant und somit O (1) -Zeit .

Wenn die Zahlen nicht gebunden sind, wächst die Überprüfungszeit mit mehr Zahlen. Theoretisch liegt dies daran, dass Ihre Prüfzeit größer ist, wenn die kleinste Zahl in der maximalen Menge groß genug wird, da Sie mehr Bits berücksichtigen müssen. Das lässt es scheinen, als wäre es etwas höher als die konstante Zeit. Sie könnten jedoch auch argumentieren, dass die Wahrscheinlichkeit, dass sich die nächste Zahl in der höchsten Menge befindet, gegen Null geht, wenn sich n der Unendlichkeit nähert, und daher nähert sich die Wahrscheinlichkeit, dass Sie mehr Bits berücksichtigen müssen, ebenfalls gegen 0, was ein Argument für O (1) wäre. Zeit.

Ich bin nicht positiv, aber mein Bauch sagt, dass es O (log (log (n))) Zeit ist. Dies liegt daran, dass die Wahrscheinlichkeit, dass die niedrigste Zahl zunimmt, logarithmisch ist und die Wahrscheinlichkeit, dass die Anzahl der Bits, die Sie für jede Prüfung berücksichtigen müssen, ebenfalls logarithmisch ist. Ich interessiere mich für andere Völker, da ich nicht wirklich sicher bin ...

Briguy37
quelle
Abgesehen davon, dass die Liste willkürlich ist, was ist, wenn es sich um eine Liste mit ständig wachsenden Zahlen handelt?
Dan_waterworth
@dan_waterworth: Wenn die unendliche Liste willkürlich ist und zufällig immer größer wird (die Wahrscheinlichkeit wäre 1 / ∞!), passt das zum Worst-Case-Szenario CheckTime + EnterTimefür jede Zahl. Dies macht nur Sinn , wenn Zahlen unbegrenzt sind, und so CheckTimeund EnterTimewird sowohl Erhöhung mindestens logarithmisch aufgrund der Zunahme der Größe der Zahlen.
Briguy37
1
Die Zahlen sind nicht zufällig, sie sind willkürlich. Es macht keinen Sinn, über Chancen zu sprechen.
Dan_waterworth
@ dan_waterworth: Du hast jetzt zweimal gesagt, dass die Zahlen willkürlich sind. Woher bekommen Sie das? Ich glaube auch, dass Sie weiterhin Statistiken auf beliebige Zahlen anwenden können, beginnend mit dem Zufallsfall, und deren Genauigkeit verbessern können, wenn Sie mehr über den Arbiter wissen. Wenn Sie beispielsweise der Schiedsrichter wären, bestünde eine größere Wahrscheinlichkeit, immer mehr Zahlen auszuwählen, als wenn ich beispielsweise der Schiedsrichter wäre;)
Briguy37,
7

Dieser ist einfach, wenn Sie Binary Heap Trees kennen . Binäre Heaps unterstützen das Einfügen in der durchschnittlichen konstanten Zeit O (1). Und geben Ihnen einfachen Zugang zu den ersten x Elementen.

Ratschenfreak
quelle
Warum sollten Sie die nicht benötigten Elemente aufbewahren? (die Werte sind zu niedrig) Scheint, als wäre ein benutzerdefinierter Algorithmus angemessener. Das heißt nicht, dass Sie die Werte nicht hinzufügen können, wenn sie nicht höher als die niedrigsten sind.
Steven Jeuris
Ich weiß nicht, meine Intuition sagt mir, dass ein Haufen (von etwas Geschmack) dies ziemlich gut schaffen könnte. Das bedeutet nicht, dass er alle Elemente behalten müsste, um dies zu tun. Ich habe es nicht recherchiert, aber es fühlt sich "richtig an" (TM).
Rig
3
Ein Heap könnte so modifiziert werden, dass er alles verwirft, was unter einer m-ten Ebene liegt (für binäre Heaps und k = 100 wäre m 7, da die Anzahl der Knoten = 2 ^ m-1). Dies würde es verlangsamen, aber es würde immer noch konstante Zeit abgeschrieben.
Plutor
3
Wenn Sie einen binären Min-Heap verwendet haben (weil dann das Top das Minimum ist, das Sie ständig überprüfen) und Sie eine neue Zahl> min finden, müssen Sie das Top-Element entfernen, bevor Sie ein neues einfügen können . Wenn Sie das oberste (min) Element entfernen, wird O (logN) angezeigt, da Sie jede Ebene des Baums einmal durchlaufen müssen. Inserts sind also nur technisch gesehen durchschnittlich O (1), da sie in der Praxis immer dann noch O (logN) sind, wenn Sie eine Zahl> min finden.
Scott Whitlock
1
@Plutor, Sie gehen von Garantien aus, die Ihnen Binärhaufen nicht geben. Visualisiert man es als binären Baum, könnte es sein, dass jedes Element im linken Zweig kleiner ist als jedes Element im rechten Zweig, aber Sie gehen davon aus, dass die kleinsten Elemente der Wurzel am nächsten liegen.
Peter Taylor
6

Wenn der Interviewer mit der Frage „Können wir sicherstellen, dass jede eingehende Nummer in konstanter Zeit verarbeitet wird“ wirklich sagen wollte, wie viele bereits darauf hingewiesen haben (siehe z. B. die Antwort von @ duedl0r), lautet die Lösung Ihres Freundes bereits O (1) und Es wäre sogar so, wenn er eine unsortierte Liste oder eine Blasensortierung oder was auch immer verwendet hätte. In diesem Fall ergibt die Frage keinen Sinn, es sei denn, es war eine knifflige Frage oder Sie erinnern sich, dass sie falsch ist.

Ich nehme an, die Frage des Interviewers war aussagekräftig, dass er nicht gefragt hat, wie man etwas zu O (1) macht, was ganz offensichtlich schon so ist.

Da die Komplexität des Fragealgorithmus nur dann sinnvoll ist, wenn die Größe der Eingabe auf unbestimmte Zeit wächst und die einzige Eingabe, die hier wachsen kann, 100 ist - die Listengröße. Ich gehe davon aus, dass die eigentliche Frage lautete: "Können wir sicherstellen, dass Top N O (1) Zeit pro Zahl ausgibt (nicht O (N) wie in der Lösung Ihres Freundes), ist das möglich?".

Das erste, was mir einfällt, ist das Zählen der Sorte, die die Komplexität von O (1) Zeit pro Zahl für das Top-N-Problem für den Preis der Verwendung des O (m) -Raums kauft, wobei m die Länge des Bereichs eingehender Zahlen ist . Also ja, das ist möglich.

hamstergene
quelle
4

Verwenden Sie eine Warteschlange mit minimaler Priorität, die mit einem Fibonacci-Heap implementiert wurde und eine konstante Einfügezeit aufweist:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)
Gabe Moothart
quelle
4
"Operationen löschen und minimale Arbeit in O(log n)amortisierter Zeit löschen " , so dass dies immer noch dazu führt, O(log k)wo kdie Menge der zu speichernden Artikel ist.
Steven Jeuris
1
Das ist nicht anders als Emilio Antwort , die die „smart-aleck Auszeichnung“ genannt wurde , da die Lösch min in arbeitet O (log n) (laut Wikipedia).
Nicole
@Renesis Emilios Antwort wäre O (k), um das Minimum zu finden, meins ist O (log k)
Gabe Moothart
1
@Gabe Fair genug, ich meine im Prinzip nur. Mit anderen Worten, wenn Sie nicht annehmen, dass 100 eine Konstante ist, dann ist diese Antwort auch keine zufriedenstellende Zeit.
Nicole
@Renesis Ich habe die (falsche) Aussage aus der Antwort entfernt.
Gabe Moothart
2

Die Aufgabe besteht eindeutig darin, einen Algorithmus zu finden, der O (1) in der Länge N der erforderlichen Liste von Zahlen ist. Es spielt also keine Rolle, ob Sie die Top-100-Nummer oder die 10000-Nummer benötigen, die Einfügezeit sollte O (1) sein.

Der Trick dabei ist, dass, obwohl diese O (1) -Anforderung für die Listeneinfügung erwähnt wird, die Frage nichts über die Reihenfolge der Suchzeit im gesamten Nummernraum aussagte, aber es stellt sich heraus, dass dies gemacht werden kann. O (1) auch. Die Lösung lautet dann wie folgt:

  1. Ordnen Sie eine Hash-Tabelle mit Zahlen für Schlüssel und Paaren verknüpfter Listenzeiger für Werte an. Jedes Zeigerpaar ist der Anfang und das Ende einer verknüpften Listenfolge. Dies ist normalerweise nur ein Element, dann das nächste. Jedes Element in der verknüpften Liste wird neben dem Element mit der nächsthöheren Nummer angezeigt. Die verknüpfte Liste enthält daher die sortierte Folge der erforderlichen Nummern. Notieren Sie sich die niedrigste Nummer.

  2. Nimm eine neue Zahl x aus dem Zufallsstrom.

  3. Ist es höher als die zuletzt aufgezeichnete niedrigste Zahl? Ja => Schritt 4, Nein => Schritt 2

  4. Schlagen Sie die Hash-Tabelle mit der gerade genommenen Nummer. Gibt es einen Eintrag? Ja => Schritt 5. Nein => Nimm eine neue Zahl x-1 und wiederhole diesen Schritt (dies ist eine einfache lineare Suche nach unten, trage mich hier ein, dies kann verbessert werden und ich werde erklären, wie)

  5. Fügen Sie mit dem soeben aus der Hash-Tabelle erhaltenen Listenelement die neue Nummer direkt nach dem Element in die verknüpfte Liste ein (und aktualisieren Sie den Hash).

  6. Nimm die niedrigste Nummer, die ich aufgezeichnet habe (und entferne sie aus dem Hash / der Liste).

  7. Schlagen Sie die Hash-Tabelle mit der gerade genommenen Nummer. Gibt es einen Eintrag? Ja => Schritt 8. Nein => Nimm eine neue Zahl l + 1 und wiederhole diesen Schritt (dies ist eine einfache lineare Suche nach oben)

  8. Bei einem positiven Treffer wird die Zahl zur neuen niedrigsten Zahl. Weiter zu Schritt 2

Um doppelte Werte zuzulassen, muss der Hash den Anfang und das Ende der verknüpften Listensequenz von Elementen, die doppelte Werte sind, beibehalten. Durch Hinzufügen oder Entfernen eines Elements zu einer bestimmten Taste wird der angezeigte Bereich vergrößert oder verkleinert.

Der Einsatz hier ist O (1). Die genannten Suchanfragen sind, denke ich, O (durchschnittlicher Unterschied zwischen Zahlen). Die durchschnittliche Differenz erhöht sich mit der Größe des Nummernraums, verringert sich jedoch mit der erforderlichen Länge der Nummernliste.

Die lineare Suchstrategie ist also ziemlich schlecht, wenn der Nummernraum groß ist (z. B. für einen 4-Byte-Int-Typ, 0 bis 2 ^ 32-1) und N = 100. Um dieses Leistungsproblem zu umgehen, können Sie parallele Sätze von Hashtabellen aufbewahren, bei denen die Zahlen auf höhere Beträge (z. B. 1s, 10s, 100s, 1000s) gerundet werden, um geeignete Schlüssel zu erstellen. Auf diese Weise können Sie einen höheren oder niedrigeren Gang einlegen, um die erforderlichen Suchvorgänge schneller durchzuführen. Die Leistung wird dann zu einem O (log numberrange), was meiner Meinung nach konstant ist, also auch zu O (1).

Stellen Sie sich zur Verdeutlichung vor, Sie hätten die Nummer 197 zur Hand. Wenn Sie den 10er-Hash-Tisch treffen, wird er mit '190' auf die nächste Zehn gerundet. Etwas? Nein. Also gehen Sie in 10s runter, bis Sie sagen 120 drücken. Dann können Sie bei 129 in der 1s-Hash-Tabelle beginnen und 128, 127 versuchen, bis Sie etwas treffen. Sie haben nun in der verknüpften Liste die Stelle gefunden, an der die Nummer 197 eingefügt werden soll. Während Sie sie eingeben, müssen Sie auch die 1s-Hashtabelle mit dem Eintrag 197, die 10s-Hashtabelle mit der Nummer 190, die 100s mit 100 usw. aktualisieren. Die meisten Schritte Sie müssen hier immer das 10-fache des Protokolls des Nummernkreises machen.

Ich könnte einige der Details falsch verstanden haben, aber da dies der Programmiereraustausch ist und der Kontext Interviews war, würde ich hoffen, dass die obige Antwort überzeugend genug für diese Situation ist.

BEARBEITEN Ich habe hier einige zusätzliche Details hinzugefügt, um das Schema der parallelen Hashtabelle zu erläutern und um zu erläutern, wie die von mir erwähnten schlechten linearen Suchen durch eine O (1) -Suche ersetzt werden können. Ich habe auch festgestellt, dass es nicht notwendig ist, nach der nächstniedrigeren Nummer zu suchen, da Sie direkt dorthin gelangen können, indem Sie in die Hash-Tabelle mit der niedrigsten Nummer schauen und zum nächsten Element übergehen.

Benedikt
quelle
1
Die Suche muss Teil der Einfügefunktion sein - es handelt sich nicht um unabhängige Funktionen. Da Ihre Suche O (n) ist, ist Ihre Einfügefunktion auch O (n).
Kirk Broadhurst
Nein. Unter Verwendung der von mir beschriebenen Strategie, bei der mehr Hashtabellen verwendet werden, um den Nummernraum schneller zu durchlaufen, ist dies O (1). Bitte lies meine Antwort noch einmal.
Benedikt
1
@Benedict, in Ihrer Antwort steht ganz klar, dass es in den Schritten 4 und 7 lineare Suchvorgänge gibt. Lineare Suchvorgänge sind nicht O (1).
Peter Taylor
Ja, aber darauf komme ich später zurück. Würde es Ihnen etwas ausmachen, den Rest zu lesen? Wenn nötig, bearbeite ich meine Antwort, um sie deutlich zu machen.
Benedikt
@Benedict Sie haben Recht - mit Ausnahme der Suche lautet Ihre Antwort O (1). Leider wird diese Lösung ohne die Suche nicht funktionieren.
Kirk Broadhurst
1

Können wir annehmen, dass die Zahlen einen festen Datentyp haben, wie z. B. Integer? Wenn ja, führen Sie eine Liste aller hinzugefügten Zahlen. Dies ist eine O (1) -Operation.

  1. Deklarieren Sie ein Array mit so vielen Elementen wie möglich:
  2. Lesen Sie jede Nummer, während sie gestreamt wird.
  3. Zählen Sie die Nummer. Ignorieren Sie es, wenn diese Zahl bereits 100-mal vergeben wurde, da Sie sie nie brauchen werden. Dies verhindert, dass Überläufe es unendlich oft zählen.
  4. Wiederholen Sie ab Schritt 2.

VB.Net Code:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Wenn Sie die Liste zurückschicken, können Sie so lange dauern, wie Sie möchten. Gehen Sie einfach vom Ende der Liste aus und erstellen Sie eine neue Liste mit den höchsten 100 aufgezeichneten Werten. Dies ist eine O (n) -Operation, die jedoch keine Rolle spielt.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Bearbeiten: In der Tat ist es egal, ob es ein fester Datentyp ist. Da der Speicherverbrauch (oder der Festplattenverbrauch) nicht begrenzt ist, können Sie diese Funktion für eine Reihe positiver Ganzzahlen verwenden.

Hand-E-Food
quelle
1

Einhundert Zahlen lassen sich leicht in einem Array der Größe 100 speichern. Jeder Baum, jede Liste oder jede Menge ist angesichts der anstehenden Aufgabe überfordert.

Wenn die eingehende Nummer höher als die niedrigste (= letzte) im Array ist, führen Sie alle Einträge durch. Wenn Sie die erste gefunden haben, die kleiner ist als Ihre neue Nummer (Sie können dazu ausgefallene Suchanfragen verwenden), durchlaufen Sie den Rest des Arrays und drücken Sie jeden Eintrag "nach unten".

Da Sie die Liste von Anfang an sortiert halten, müssen Sie überhaupt keinen Sortieralgorithmus ausführen. Das ist O (1).

Jörg Z.
quelle
0

Sie könnten einen binären Max-Heap verwenden. Sie müssten einen Zeiger auf den minimalen Knoten verfolgen (der unbekannt / null sein könnte).

Sie beginnen, indem Sie die ersten 100 Zahlen in den Heap einfügen. Das Maximum wird oben sein. Nachdem dies erledigt ist, werden Sie immer 100 Nummern darin behalten.

Wenn Sie dann eine neue Nummer erhalten:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Leider findMinimumNodeist O (n) und es fallen einmalig Kosten pro Insert an (aber nicht während des Inserts :). Das Entfernen des Mindestknotens und das Einfügen des neuen Knotens haben im Durchschnitt den Wert O (1), da sie zum unteren Rand des Heaps tendieren.

Wenn Sie einen binären Min-Heap verwenden, befindet sich der Min-Heap ganz oben, was sich hervorragend dazu eignet, den Min-Heap zum Vergleich zu ermitteln. Dies ist jedoch kein Erfolg, wenn Sie den Minimum-Heap durch eine neue Zahl ersetzen müssen, die> min ist. Das liegt daran, dass Sie den min-Knoten (immer O (logN)) entfernen und dann den neuen Knoten einfügen müssen (durchschnittliches O (1)). Sie haben also immer noch O (logN), was besser ist als Max-Heap, aber nicht O (1).

Wenn N konstant ist, haben Sie natürlich immer O (1). :)

Scott Whitlock
quelle