Median Queue implementieren

[InformaticStudent]

Hallo zusammen, hättet ihr einen Ansatz zu der folgenden Aufgabe:

Für die Zwecke dieser Aufgabe ist der Median einer Menge S von n verschiedenen Schlüsseln definiert als der [n/2]-kleinste Schlüssel in S.
Also der Median von {8,6,9} ist 8. Außerdem können Sie davon ausgehen, dass alle vorkommenden Schlüssel verschieden sind.
Eine Median-Queue verwaltet eine endliche Menge S von Schlüsseln unter folgenden Operationen:
ISEmpty (IS), Insert (k,s) Median (s) und DeleteMedian (s). Diese Operationen haben die offensichtlichen Bedeutungen.
Die beiden letzten sind nur anwendbar, wenn S nicht leer ist. Median (S) gibt nur einen Wert zurück, wohingegen DeleteMedian (s) die Menge S verändert.

1. Entwerfen Sie eine Datenstruktur, die so eine Median-Queue realisiert. Welche Laufzeiten können Sie für die Operationen erzielen? (Je kleiner, desto besser!).
Gelten die Laufzeiten worst-case, erwartet oder amortisiert?
2. Wie würden Sie in Ihrer Datenstruktur DecreaseKey und IncreaseKey Operationen realisieren und welche Laufzeiten können Sie dafür erzielen?

Ich stehe hier extrem auf dem Schlauch und wäre sehr dankbar für jede Hilfe da diese Aufgabe mal eine Klausuraufgabe war! Danke schonmal!

 

[osion]

Eine Möglichkeit, um eine Median-Queue zu realisieren, wäre die Verwendung von zwei Heaps: einen Min-Heap und einen Max-Heap. Der Min-Heap speichert die kleineren Hälfte der Schlüssel und der Max-Heap speichert die größeren Hälfte. Die Insert-Operation kann in O(log n) realisiert werden, indem der neue Schlüssel dem entsprechenden Heap hinzugefügt wird. Die ISEmpty-Operation kann in O(1) realisiert werden, indem geprüft wird, ob beide Heaps leer sind. Die Median-Operation kann in O(1) realisiert werden, indem der Wurzelknoten des Heaps mit den größeren Schlüsseln zurückgegeben wird, da dieser immer der [n/2]-kleinste Schlüssel in S ist. Die DeleteMedian-Operation kann in O(log n) realisiert werden, indem der Wurzelknoten des Heaps mit den größeren Schlüsseln entfernt wird und der neue Median aus dem anderen Heap extrahiert wird.

Die DecreaseKey- und IncreaseKey-Operationen können in O(log n) realisiert werden, indem der Schlüssel im entsprechenden Heap angepasst wird und die Heap-Eigenschaft wiederhergestellt wird. Die Laufzeiten sind worst-case, da sie sich auf das schlechteste Szenario beziehen, in dem alle Operationen ihre maximale Laufzeit benötigen.

 

[Oneixee5]

Der Min-Heap speichert die kleineren Hälfte der Schlüssel und der Max-Heap speichert die größeren Hälfte.

Nur um das richtig zu verstehen: Man muss zuerst herausfinden, was die Hälfte ist also den Median um die Werte der Menge S dem richtigen Heap zuzuordnen?

 

[osion]

Ja, das ist richtig. Um eine Median-Queue zu realisieren, muss man zunächst die Mitte der Menge S bestimmen, um den Median zu bestimmen und die Werte der Menge S dem entsprechenden Heap zuzuordnen.

Vorgehen:

• Zähle die Anzahl der Schlüssel in der Menge S.
• Berechne den Median als den [n/2]-kleinsten Schlüssel, wobei n die Anzahl der Schlüssel in S ist.
• Füge jeden neuen Schlüssel der Menge S dem entsprechenden Heap hinzu, abhängig von seiner Größe im Vergleich zum Median. Der Min-Heap speichert die kleineren Hälfte der Schlüssel und der Max-Heap speichert die größeren Hälfte

 

[Oneixee5]

Das ist doch eine Antwort aus ChatGPT

 

[Oneixee5]

Ich würde es so in der Art umsetzen:

public class Test {

    /**
     * "Der Median der Messwerte einer Urliste ist derjenige Messwert, der genau „in der Mitte“ steht, wenn man die
     * Messwerte der Größe nach sortiert. ... Wenn die Anzahl der Werte gerade ist, wird der Median meist als
     * arithmetisches Mittel der beiden mittleren Zahlen definiert, die dann Unter- und Obermedian heißen." - Quelle:
     * Wikipedia <br>
     * <br>
     * Das Letzere wird hier nicht so umgesetzt, da sonst {@link #deleteMedian()} keinen Sinn macht.
     */
    private static final class MedianQueue {

        private final ArrayList<Integer> sorted = new ArrayList<>();

        MedianQueue(final Collection<Integer> elements) {
            this.sorted.addAll(elements);
            Collections.sort(this.sorted);
        }

        boolean insert(final Integer e) {
            final boolean b = this.sorted.add(e);
            if (b) {
                Collections.sort(this.sorted);
            }
            return b;
        }

        boolean isEmpty() {
            return this.sorted.isEmpty();
        }

        private int getMiddle() {
            final int middle = this.sorted.size() / 2;
            return middle > 0 && middle % 2 == 0 ? middle - 1 : middle;
        }

        Integer getMedian() {
            if (isEmpty()) {
                throw new IllegalStateException("MedianQueue is empty!");
            }
            return this.sorted.get(getMiddle());
        }

        void deleteMedian() {
            if (isEmpty()) {
                throw new IllegalStateException("MedianQueue is empty!");
            }
            this.sorted.remove(getMiddle());
        }

        @Override
        public String toString() {
            return this.sorted.toString();
        }

    }

    public static void main(final String[] args) {

        final List<Integer> menge = List.of(8, 6, 9);
        final MedianQueue sorted = new MedianQueue(menge);

        System.out.println(sorted.getMedian());

        sorted.deleteMedian();
        sorted.insert(7);

        System.out.println(sorted.getMedian());

        System.out.println(sorted);
    }

}