Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Median-Queue Datenstruktur
Autor
Universität/Hochschule Median-Queue Datenstruktur
InformaticStudent
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2021
Mitteilungen: 7
  Themenstart: 2021-03-19

Für die Zwecke dieser und der nächsten 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,10}$ ist $8$ und der Median von ${2,5,9,11,14,10}$ ist $9$. Außerdem können Sie für die Zwecke dieser Aufgaben davon ausgehen, dass alle vorkommenden Schlüssel verschieden sind. Eine Median-Queue verwaltet eine endliche Menge $S$ von Schlüsseln unter folgenden Operationen: $ISEMPTY(S)$, $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, wogegen $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 $4$ Operationen erzielen? (Je kleiner desto besser!) Gelten die Laufzeiten worst-case, erwartet oder amortisiert? 2.Wie würden Sie Ihrer Struktur $DECREASEKEY$ und $INCREASEKEY$ Operationen realisieren und welche Laufzeiten könnten Sie dafür erzielen?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3040
  Beitrag No.1, eingetragen 2021-03-20

Was hast du dir denn bisher dazu gedacht? Tipp: Nehmen wir an, die Struktur enthält mindestens 3 Elemente. - Welche Invariante gilt dann für die Nachbarn des Median? - Was ist zu tun, um diese nach Einfügen/Löschen/etc. zu erhalten?


   Profil
InformaticStudent hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]