Geordnete Arrays - Implementation

[Dirty Oerti]

Tag!
Nachdem Paging nun (zur Zeit befriedigend gut) funktioniert, möchte ich natürlich weitermachen
Jetzt geht es dann daran, einen Heap zu schreiben.
Um einen Heap zu implementieren, und auch später, werde ich geordnete Arrays brauchen.
Also schreibe ich mir dafür mal Funktionen.

Problem: Wie implementiere ich das möglichst gut? Will heißen möglichst schnell?
Gibt es irgendwo Code dazu, den ich mir mal anschauen könnte?

Ich habe zwar eine Vorlage (HIER), allerdings möchte ich gerne unterschiedliche Möglichkeiten sehen, bevor ich mich für eine entscheide.
Außerdem:

There are better implementations of ordered arrays than this (c.f. heap-ordering, binary search trees), but I decided to go with a simple one for teaching purposes.

Diese einfache Implementation habe ich verstanden. Nun will ich mehr ( ). Und zwar bessere, schneller Arten der Implementation.

Kennt sich da jemand aus?

*edit an andere Moderatoren* Soll ich das hier drinn lassen, oder kommt das besser in Algorithmen und Konzepte?*/edit*
*edit2* Ich hab's mal verschoben. Das passt hier doch besser */edit2*

EDIT:
Es müssen nicht unbedingt geordnete Arrays sein.

Ich brauche irgendetwas, um eine Suchfunktion möglichst gut zu implementieren.
Ich habe mir auch schon Binäre Bäume angesehen, weiß aber nicht so recht, wie ich das in meinem Fall verwirklichen könnte.
Das Problem dabei ist, dass ich z.B. nach dem Wert 4 suche.
Falls es genau diesen Wert nun nicht gibt, dann möchte ich den nächste größeren Wert bekommen, der am nächsten drann ist.

Ideen?

[cloidnerux]

Sortire doch nach dem AscII code.
Du nimmst ein Zweidimensionalen Array ungefär so

Code: Alles auswählen

long int liste[255][1[hier schreibst du den Link zu ein array eines bestimmten anfangs]

die 255 ssteht natürlich alle ascii zeichen. z.B in

Code: Alles auswählen

liste['a''(97)]

stehen natürlich alle elemente die mit a anfangen. In der zweiten dimension stehen natürlich die Adressen der Array einzelnener gruppen.
Wenn du jezt nach 'abcd' suchst, dann suchst du anch etwas das mit 'a' anfängt also muss du in liste[97/'a'] schauen. Das würde die PErformance Totall erhöhen.

[Dirty Oerti]

Ich brauche eine dynamische Liste, die sich in der Größe verändern kann.

Das würde die PErformance Totall erhöhen.

Da bin ich mir nicht unbedingt so sicher.

[cloidnerux]

Hast du mal vectoren unter C++ gesehn. Das wäre villeicht etwas für dich.
Das Problem ist ja, wenn du ein Elemnt hinzufügst, wilst du das nichtr am ende, sondern da mchen wo er hingehört, also müsstetst du alle anderen element um x nach hintenschiebern

[Dirty Oerti]

Wenn ich alle anderen verschieben muss, ist das nicht gerade schnell.
Aber vectoren?
Kernelprogrammieren?
No way...

[cloidnerux]

Es ist nur ein vorschlag

Wie groß soll denn so eine Liste sein?
Für 20-50 Einträge wäre sowas noch möglich, aber für mehr musst du natürlich was besseres programmieren.

[taljeth]

Ich brauche irgendetwas, um eine Suchfunktion möglichst gut zu implementieren.
Ich habe mir auch schon Binäre Bäume angesehen, weiß aber nicht so recht, wie ich das in meinem Fall verwirklichen könnte.
Das Problem dabei ist, dass ich z.B. nach dem Wert 4 suche.
Falls es genau diesen Wert nun nicht gibt, dann möchte ich den nächste größeren Wert bekommen, der am nächsten drann ist.

Hm, wozu das? Aber auch das ist nicht besonders schwer, wenn du in jedem Knoten noch einen Verweis auf den Vaterknoten drin hast (aber das braucht es genau genommen nichtmal - erst, wenn du von beliebigen Knoten den Vorgänger oder Nachfolger willst). Erstmal bis ganz nach unten durchhangeln ist ja kein Problem. Entweder du hast deine 4 dann, oder du suchst den nächstgrößeren Wert. In letzterem Fall prüfen, ob der Knoten, an dem du rausgekommen bist, größer ist (wenn ja => fertig), ansonsten zum Vaterknoten gehen (=> auch fertig).

Einfach nur binäre Bäume sind leicht zu implementieren. Schwierig wird es erst dann, wenn du irgendwelche Vorkehrungen willst, daß die Bäume nicht entarten. Also Stichwort AVL-Bäume oder Rot-Schwarz-Bäume.

Und wegen der passenden Datenstruktur solltest du dir vielleicht erstmal überlegen, was die Anforderungen wirklich sind. Geordnete Arrays sind beispielsweise toll zum drin suchen, aber nicht mehr ganz so toll, wenn es um einfügen oder löschen geht. In Bäume kann man schnell einfügen, aber sie brauchen mehr Platz. Und so weiter.