Heapsort mit binärer Suche

[Zwickl-Pain]

Hej Ihr,
für ein Praktikum muss ich derzeit diverse Suchalgorithmen implementieren...

Das meiste krieg ich halbwegs hin, jedoch hab ich überhaupt keine Idee wie ich den Heapsort mit binärer Suche zusammenschuster
Binäre Suche braucht meines Wissens nach ein bereits sortiertes Array welches ich ja im Heapaufbau nicht erzeuge.

Hat jemand von euch Ahnung wie der Heapsort mit binärer Suche funzt?

Falls jemand Code hätte wäre das fein, aber mit einer verständlichen Erklärung wäre mir sehr geholfen... Hab bisher nur ein Script von der TU-Ilmenau gefunden, jedoch versteh ich da nur Bahnhof

Vielen Dank schonmal, falls sich jemand die Mühe macht

 

[BullshitBingo]

Hi,

also hier finde ich das schon sehr anschaulich erklärt. Die Links am Ende des Artikels sind auch sehr hilfreich. Hoffe, es bringt dich weiter!

 

[IceMatrix]

wie lautet die genaue aufgabenstellung?

 

[Zwickl-Pain]

Aufgabe: HeapSort mit binärer Suche implementieren
Die auf Wiki sehe ich nicht als binäre an, bzw. ich checks nicht ^^
Einen linearen HeapSort krieg ich hin, doch wie ich da die binäre Suche einwursteln könnte entzieht mir jeder Kenntnis... Die binäre Suche benötigt meines Wissens nach ein Sortiertes Array und der Heap ist ja nicht "sortiert" :-\

 

[mensch183]

Aufgabe: HeapSort mit binärer Suche implementieren
Die auf Wiki sehe ich nicht als binäre an, bzw. ich checks nicht ^^

Die vielen bebilderten Beispiele zeigen Bäume, deren Knoten immer 2 Kinder haben. Weil es 2 sind, nennt man den Baum einen Binärbaum und das darauf basierende Sortierverfahren auch binär. Du siehst also genau das Verfahren, was du implementieren sollst.

Erst weiter untern steht was zu ternären Bäumen (3 Kinder) und Bäumen noch höherer Ordnung.

 

[Zwickl-Pain]

Hmm, die bebilderten Beispiele sind aber lineare Heaps, zumindest hat das mein Prof so erklärt.... Die bebilderten Beispiele sind kein Thema, die hab ich schon am laufen.
So wie ich dies verstanden haben kann man mittels der binären Suche das einsickern umgehen, doch wie entzieht sich meiner Kenntnis

Die auf Wikipedia angeführten Beispiele hab ich mittels DownHeap implementiert (n mit n*2 & n*2+1 vergleichen)

Naja, ich probier noch ein wenig rum ^^