Mengenoperationen

[Peter2]

:?:
Hallo ihr!

Ich tue mich schwer mit den Mengenoperationen in Java!
Ich soll zu jeder der folgenden Methoden eine Datenstruktur nennen, bei der diese Methode besonders effizient implementiert werden kann und das dann auch noch meine Wahl begründen.
Ich wäre für hilfe sehr dankbar!

a)

void insert(Comparable)

Einfügen eines Elements in die Menge.

b)

void remove(Comparable)

Entfernen eines Elements aus einer Menge.

c)

Comparable accessMin()

Das kleinste Element einer Menge zurückgeben.

d)

boolean contains(Comparable)

Enhält die Menge das gefragte Element.

e)

Comparable successor(Comparable)

Nachfolger eines Elements zurückgeben.

f)

Comparable kthElement(int k)

Das k-te Element zurückgeben.

 

[nollario]

hm.... nicht so einfach....

zunächst einmal : was meinst du mit datenstrukturen? im zweifelsfall ist man immer am schnellsten wenn man ein array nutzt, da man sich dann überflüssige casts spart, die bei den anderen java collections nötig. also schliesse ich arrays zunächst einmal aus...

also e) den successor holen, das geht mit einer verketteten liste (LinkedList) wohl sehr effizient, da jedes Objekt seinen successor "kennt"

bei den anderen könnte ich nicht auf anhieb sagen, welches am sinnvollsten ist: hängt zum einen auch daran, dass der inhalt der collections entscheidend ist.... und zum anderen gibt es ja doch ne ecke collection implementierungen...

 

[bygones]

da gibts einige möglichkeiten - hier eine kleine Auswahl

Für die Methoden insert / remove / contains / first (accessMin) ist z.b das TreeSet (u.a. da du mit Comparable arbeitest) gut

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains)

Wie es mit dem successor bzw. kth Element ist - da denk ich ist TreeSet nicht so gut. kth Element wäre bei einer Array basierten Struktur geht weil schneller zugriff (z.b. ArrayList).

Ich persönlich würde wahrscheinlich für alle Methoden eine Priority Queue nehmen (z.b. Fibonacci - Heap) - die sind für solche Operationen meist optimiert