Median des Streams von Ganzzahlen mit Heap in Java

1. Übersicht

In diesem Tutorial lernen wir, wie man den Median eines Stroms von ganzen Zahlen berechnet.

Wir werden das Problem anhand von Beispielen angeben, das Problem analysieren und schließlich mehrere Lösungen in Java implementieren.

2. Problemstellung

Der Median ist der Mittelwert eines geordneten Datensatzes. Für eine Reihe von Ganzzahlen gibt es genauso viele Elemente, die kleiner als der Median sind, wie größer.

In einem bestellten Satz von:

  • ungerade Anzahl von ganzen Zahlen, das mittlere Element ist der Median - in der geordneten Menge {5, 7, 10} ist der Median 7
  • Gerade Anzahl von ganzen Zahlen, es gibt kein mittleres Element; Der Median wird als Durchschnitt der beiden mittleren Elemente berechnet - in der geordneten Menge {5, 7, 8, 10} beträgt der Median (7 + 8) / 2 = 7,5

Nehmen wir nun an, dass wir anstelle einer endlichen Menge ganze Zahlen aus einem Datenstrom lesen. Wir können den Median eines Stroms von Ganzzahlen als den Median der Menge der bisher gelesenen Ganzzahlen definieren .

Lassen Sie uns die Problemstellung formalisieren. Bei einer Eingabe eines Stroms von Ganzzahlen müssen wir eine Klasse entwerfen, die für jede gelesene Ganzzahl die folgenden zwei Aufgaben ausführt:

  1. Fügen Sie die Ganzzahl zur Menge der Ganzzahlen hinzu
  2. Finden Sie den Median der bisher gelesenen ganzen Zahlen

Zum Beispiel:

add 5 // sorted-set = { 5 }, size = 1 get median -> 5 add 7 // sorted-set = { 5, 7 }, size = 2 get median -> (5 + 7) / 2 = 6 add 10 // sorted-set = { 5, 7, 10 }, size = 3 get median -> 7 add 8 // sorted-set = { 5, 7, 8, 10 }, size = 4 get median -> (7 + 8) / 2 = 7.5 .. 

Obwohl der Stream nicht endlich ist, können wir davon ausgehen, dass wir alle Elemente des Streams gleichzeitig im Speicher halten können.

Wir können unsere Aufgaben als die folgenden Operationen im Code darstellen:

void add(int num); double getMedian(); 

3. Naiver Ansatz

3.1. Sortierte Liste

Beginnen wir mit einer einfachen Idee: Wir können den Median einer sortierten Liste von Ganzzahlen berechnen, indem wir auf das mittlere Element oder die beiden mittleren Elemente der Liste nach Index zugreifen . Die zeitliche Komplexität der getMedian- Operation beträgt O (1) .

Beim Hinzufügen einer neuen Ganzzahl müssen wir die korrekte Position in der Liste ermitteln , damit die Liste sortiert bleibt. Diese Operation kann in O (n) -Zeit ausgeführt werden, wobei n die Größe der Liste ist . Die Gesamtkosten für das Hinzufügen eines neuen Elements zur Liste und das Berechnen des neuen Medians betragen also O (n) .

3.2. Verbesserung des naiven Ansatzes

Die Additionsoperation wird in linearer Zeit ausgeführt, was nicht optimal ist. Versuchen wir, dies in diesem Abschnitt zu beheben.

Wir können die Liste in zwei sortierte Listen aufteilen - die kleinere Hälfte der Ganzzahlen in absteigender Reihenfolge und die größere Hälfte der Ganzzahlen in aufsteigender Reihenfolge . Wir können der entsprechenden Hälfte eine neue Ganzzahl hinzufügen, sodass sich die Größe der Listen um höchstens 1 unterscheidet:

if element is smaller than min. element of larger half: insert into smaller half at appropriate index if smaller half is much bigger than larger half: remove max. element of smaller half and insert at the beginning of larger half (rebalance) else insert into larger half at appropriate index: if larger half is much bigger than smaller half: remove min. element of larger half and insert at the beginning of smaller half (rebalance) 

Jetzt können wir den Median berechnen:

if lists contain equal number of elements: median = (max. element of smaller half + min. element of larger half) / 2 else if smaller half contains more elements: median = max. element of smaller half else if larger half contains more elements: median = min. element of larger half

Obwohl wir die zeitliche Komplexität der Additionsoperation nur um einen konstanten Faktor verbessert haben, haben wir Fortschritte erzielt.

Lassen Sie uns die Elemente analysieren, auf die wir in den beiden sortierten Listen zugreifen . Wir greifen möglicherweise auf jedes Element zu, wenn wir es während des (sortierten) Addiervorgangs verschieben . Während der noch wichtiger ist , greifen wir auf das Minimum und Maximum (extremums) der größeren und kleineren Hälften jeweils Add Operation für Rebalancing und während der getMedian Betrieb.

Wir können sehen, dass Extreme die ersten Elemente ihrer jeweiligen Listen sind . Daher müssen wir den Zugriff auf das Element bei Index 0 für jede Hälfte optimieren , um die Gesamtlaufzeit der Additionsoperation zu verbessern .

4. Heap- basierter Ansatz

Lassen Sie uns unser Verständnis des Problems verfeinern, indem wir das anwenden, was wir aus unserem naiven Ansatz gelernt haben:

  1. Wir müssen das minimale / maximale Element eines Datensatzes in O (1) -Zeit erhalten
  2. Die Elemente müssen nicht in einer sortierten Reihenfolge gehalten werden, solange wir das minimale / maximale Element effizient erhalten können
  3. Wir müssen einen Ansatz finden, um unserem Datensatz ein Element hinzuzufügen, das weniger als O (n) Zeit kostet

Als nächstes betrachten wir die Heap-Datenstruktur, mit deren Hilfe wir unsere Ziele effizient erreichen können.

4.1. Heap-Datenstruktur

Heap ist eine Datenstruktur, die normalerweise mit einem Array implementiert wird, aber als Binärbaum betrachtet werden kann .

Heaps werden durch die Heap-Eigenschaft eingeschränkt:

4.1.1. Max - Heap - Eigenschaft

Ein (untergeordneter) Knoten kann keinen größeren Wert als den seines übergeordneten Knotens haben. Daher hat in einem Max-Heap der Wurzelknoten immer den größten Wert.

4.1.2. Min - Heap - Eigenschaft

Ein (übergeordneter) Knoten kann keinen größeren Wert als den seiner untergeordneten Knoten haben. Somit hat in einem Min-Heap der Wurzelknoten immer den kleinsten Wert.

In Java repräsentiert die PriorityQueue- Klasse einen Heap. Fahren wir mit unserer ersten Lösung fort, bei der Haufen verwendet werden.

4.2. Erste Lösung

Ersetzen wir die Listen in unserem naiven Ansatz durch zwei Haufen:

  • Ein Min-Heap, der die größere Hälfte der Elemente enthält, wobei sich das minimale Element an der Wurzel befindet
  • Ein Max-Heap, der die kleinere Hälfte der Elemente enthält, wobei sich das maximale Element im Stammverzeichnis befindet

Jetzt können wir die eingehende Ganzzahl zur relevanten Hälfte hinzufügen, indem wir sie mit der Wurzel des Min-Heaps vergleichen. Wenn sich die Größe eines Heaps nach dem Einfügen um mehr als 1 von der des anderen Heaps unterscheidet, können wir die Heaps neu ausbalancieren und so einen Größenunterschied von höchstens 1 beibehalten:

if size(minHeap) > size(maxHeap) + 1: remove root element of minHeap, insert into maxHeap if size(maxHeap) > size(minHeap) + 1: remove root element of maxHeap, insert into minHeap

Mit diesem Ansatz können wir den Median als Durchschnitt der Wurzelelemente beider Heaps berechnen, wenn die Größe der beiden Heaps gleich ist. Andernfalls ist das Stammelement des Heaps mit mehr Elementen der Median .

Wir werden die PriorityQueue- Klasse verwenden, um die Heaps darzustellen. Die Standard-Heap-Eigenschaft einer PriorityQueue ist min-heap. Wir können einen Max-Heap erstellen, indem wir einen Comparator.reverserOrder verwenden, der die Umkehrung der natürlichen Reihenfolge verwendet:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (!minHeap.isEmpty() && num  minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } } else { minHeap.offer(num); if (minHeap.size() > maxHeap.size() + 1) { maxHeap.offer(minHeap.poll()); } } } double getMedian() { int median; if (minHeap.size()  maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

Bevor wir die Laufzeit unseres Codes analysieren, schauen wir uns die zeitliche Komplexität der von uns verwendeten Heap-Operationen an:

find-min/find-max O(1) delete-min/delete-max O(log n) insert O(log n) 

Daher kann die getMedian- Operation in O (1) -Zeit ausgeführt werden, da nur die Funktionen find-min und find-max erforderlich sind . Die zeitliche Komplexität der Additionsoperation beträgt O (log n) - drei Einfüge- / Löschaufrufe, die jeweils O (log n) Zeit erfordern .

4.3. Heap Size Invariant Solution

In unserem vorherigen Ansatz haben wir jedes neue Element mit den Stammelementen der Heaps verglichen. Lassen Sie uns einen anderen Ansatz mit Heap untersuchen, bei dem wir die Heap-Eigenschaft nutzen können, um ein neues Element in der entsprechenden Hälfte hinzuzufügen.

Wie bei unserer vorherigen Lösung beginnen wir mit zwei Heaps - einem Min-Heap und einem Max-Heap. Als nächstes führen wir eine Bedingung ein: Die Größe des Max-Heaps muss immer (n / 2) sein, während die Größe des Min-Heaps entweder (n / 2) oder (n / 2) + 1 sein kann. abhängig von der Gesamtzahl der Elemente in den beiden Haufen . Mit anderen Worten, wir können nur dem Min-Heap erlauben, ein zusätzliches Element zu haben, wenn die Gesamtzahl der Elemente ungerade ist.

Mit unserer Heap-Größeninvariante können wir den Median als Durchschnitt der Stammelemente beider Heaps berechnen, wenn die Größe beider Heaps (n / 2) beträgt . Andernfalls ist das Stammelement des Min-Heaps der Median .

Wenn wir eine neue Ganzzahl hinzufügen, haben wir zwei Szenarien:

1. Total no. of existing elements is even size(min-heap) == size(max-heap) == (n / 2) 2. Total no. of existing elements is odd size(max-heap) == (n / 2) size(min-heap) == (n / 2) + 1 

We can maintain the invariant by adding the new element to one of the heaps and rebalancing every time:

The rebalancing works by moving the largest element from the max-heap to the min-heap, or by moving the smallest element from the min-heap to the max-heap. This way, though we're not comparing the new integer before adding it to a heap, the subsequent rebalancing ensures that we honor the underlying invariant of smaller and larger halves.

Let's implement our solution in Java using PriorityQueues:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (minHeap.size() == maxHeap.size()) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); } else { minHeap.offer(num); maxHeap.offer(minHeap.poll()); } } double getMedian() { int median; if (minHeap.size() > maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

The time complexities of our operations remain unchanged: getMedian costs O(1) time, while add runs in time O(log n) with exactly the same number of operations.

Beide Heap-basierten Lösungen bieten ähnliche räumliche und zeitliche Komplexität. Während die zweite Lösung clever ist und eine sauberere Implementierung aufweist, ist der Ansatz nicht intuitiv. Andererseits folgt die erste Lösung natürlich unserer Intuition, und es ist einfacher, über die Richtigkeit der Additionsoperation nachzudenken.

5. Fazit

In diesem Tutorial haben wir gelernt, wie man den Median eines Stroms von ganzen Zahlen berechnet. Wir haben einige Ansätze evaluiert und mit PriorityQueue verschiedene Lösungen in Java implementiert .

Wie üblich ist der Quellcode für alle Beispiele auf GitHub verfügbar.