Prioritätswarteschlange, wo Werte eine Summe von zwei Währungen sind und popMin einen Wechselkurs verwendet

Question

Ich möchte eine Prioritätswarteschlange definieren, in der Prioritäten Komponenten in zwei verschiedenen Währungen enthalten. Zum Beispiel kostet Artikel A 1 USD + 20 Yen. Diese Warteschlange hat zwei Methoden, insert(priceInUsd, priceInYen) und popMin(exchangeRate), die einen Preis von einem US-Dollar in Yen kostet und den Artikel mit den niedrigsten Gesamtkosten in USD und Yen bei diesem Wechselkurs veröffentlicht. Wie implementiere ich das?

Hier sind Ideen meine bisher:

• einen k-d-Baum verwenden. Die Einfügung dauert log (n). Ich denke, Sie können findMin durch eine geringfügige Änderung am normalen k-d-Baum-Nearest-Neighbor-Algorithmus implementieren, also sollte dies angeblich log (n) Zeit dauern. Wikipedia ist eine Art Hedge, ob k-d Baum nächster Nachbar ist wirklich log (n) schlimmsten Fall, wenn Sie schreckliche Daten haben, so bin ich mir nicht sicher. Außerdem habe ich noch nie einen besonders zuverlässig aussehenden Quellennachweis gesehen, dass kd-Bäume eine Log (n) -Einfügung erlauben.
• Behalten Sie die konvexe Hülle der Punkte und Schleife über alles darin, wenn Sie wollenMin. Worst Case n, aber wenn es normalerweise nur n**(1/3) Dinge in Ihrer konvexen Hülle gibt, ist das im Durchschnitt in Ordnung.

Answer 1

Es gibt einige Stand der Technik, die Sie nicht erwähnt haben, auf dem dynamic planar convex hull Problem. Brodal and Jacob (FOCS '02) geben Sie eine Datenstruktur, mit der Sie einen Punkt einfügen, einen Punkt löschen und den Extrempunkt in einer Richtung in amortisierter logarithmischer Zeit finden können, was ausreicht, um Ihre Datenstruktur zu implementieren (obwohl die Implementierung kompliziert aussieht).

Answer 2

Hier ist eine einfache Antwort, die O (√n) -Zeiteinfügungen und O (√n Log n) -Zeit Pop-Minuten bietet.

Punkte werden in einem von O (√n) Bins aufbewahrt. Jeder Behälter hat eine für ihn berechnete konvexe Hülle, die in der Reihenfolge atan2(yen, usd) gespeichert ist (obwohl Sie keine Triggerung benötigen, um zwei Punkte zu vergleichen). Die Füllreihenfolge für Einsätze ist wie folgt:

Bin 0: 0 2 5 9 14 
Bin 1: 1 4 8 13 
Bin 2: 3 7 12 
Bin 3: 6 11 
Bin 4: 10 
... 

einen Punkt einzufügen, es einen Behälter zuzuordnen, und die konvexe Hülle für diesen Behälter neu zu berechnen. Dies ist O (√ n) -zeit, wenn Sie die Punkte in sortierter Reihenfolge des Winkels in einem Array halten und einen Graham-Scan erneut ausführen.

Zu pop-min finden wir den zu löschenden Punkt, löschen ihn und ersetzen ihn durch einen Punkt aus einem anderen Bin, um die richtigen Bin-Größen zu erhalten (nach einer Insertion ist dies der Bin, der war gerade eingefügt). Der interessante Teil dieser Operation ist das Finden. Um den minimalen Gesamtwert für einen bestimmten Wechselkurs auf der konvexen Hülle zu finden, benutze die binäre Suche, um den Vorgänger und den Nachfolger auf dem Rumpf in Bezug auf die Winkelreihenfolge zu finden, und gebe dann das Minimum dieser beiden zurück.