Hallo,
in einer Klausur wird eine Frage gestellt, die nur mit Ja oder Nein beantwortet werden muss:
Kann in einem Heap mit n Elementen das k-kleinste Element in O(log k) gefunden werden??
Nein, oder??
Denn für das 1-kleinste Element muss man den längsten Pfad im Heap folgen und das ist nicht .
Felix
Hallo Felix
in einer Klausur wird eine Frage gestellt, die nur mit Ja oder
Nein beantwortet werden muss:
Kann in einem Heap mit n Elementen das k-kleinste Element in
O(log k) gefunden werden??
Nein, oder??
Denn für das 1-kleinste Element muss man den längsten Pfad im
Heap folgen und das ist nicht .
NEIN
Ein Heap ist ein spezieller Speicherbereich und diese Bezeichnung sagt nichts über die Organisation der Daten aus. Bei einem Sortierten Datenbestand knn man das k-kleinset Element mit einem Zugrif finden da es an der Position k steht.
MfG Peter(TOO)
Hallo Peter,
NEIN
Ein Heap ist ein spezieller Speicherbereich und diese
Bezeichnung sagt nichts über die Organisation der Daten aus.
die Bezeichnung „Heap“ wird in zwei verschiedenen Zusammenhängen benutzt:
Für den vom Laufzeitsystem verwalteten freien Speicher, wo z. B. dynamische Datenstrukturen angelegt werden;
Für einen abstrakten Datentyp („ADT“) mit bestimmten Eigenschaften. Dabei handelt es sich um eine besondere Klasse binärer Bäume. Deutsche Bezeichnungen für „Heap“ sind „Haufen“ oder „Halde“ (werden aber kaum gebraucht). Da sich ein Heap auch als sogenannte Prioritätswarteschlange interpretieren läßt, wird er manchmal auch „priority queue“ genannt.
Der bekannteste Algorithmus, der auf dem ADT „Heap“ basiert, ist der Sortieralgorithmus „Heapsort“. Die genaue Definition eines Heaps und die Erklärung, wie Heapsort funktioniert, findest Du hier:
http://www.iti.fh-flensburg.de/lang/algorithmen/sort…
Mit freundlichem Gruß
Martin
PS: Um Felix’ Frage zu beantworten, reichen meine Kenntnisse leider nicht aus – sorry.
Hallo Felix,
Denn für das 1-kleinste Element muss man den längsten Pfad im
Heap folgen und das ist nicht .
Nicht unbedingt. Zwar wird in den meisten Algorithmenbüchern ein Heap so dargestellt, dass die Wurzel das grösste Element ist und alle Nachfolger eines Knoten kleiner sein müssen als der Knoten. Allerdings könnte der Heap auch genau anders herum organisiert werden, d.h. kleinste Zahl an der Wurzel, alle Nachfolger größer als ein Knoten. Dann muss nur noch das „Sinken“ von Knoten angepasst werden. Heapsort würde dann eine aufsteigend sortierte Zahlenfolge ausgeben.
Allerdings glaube ich, dass die Aussage i-kleinstes Element in O(log i) Schritten trotzdem mit nein zu beantworten ist.
Für das n-kleinste Element hiesse das ja O(log n). An einem Knoten habe ich nur die Information, dass alle Nachfolger kleiner sind. Jedoch weiss ich nicht, in welchem meiner Teilbäume das Minimum liegt. Für das Ablaufen eines beliebigen Pfades bis zur Wurzel benötige ich jedoch bereits log n Schritte (das ist ja gerade die Länge dieses Pfades bei einem Binärbaum).
Auch wenn mein Heap als Array organisiert ist, kann ich das n-kleinste Element nicht schnell finden. Das n-kleinste ist per Definition ein Blatt (es kann keine Nachfolger haben). Ein Heap mit n Knoten hat ~n/2~ Blätter, das heisst das n-kleinste ist nur in O(n) Schritten zu finden (~ bedeute das kleinste ganze grösser gleich).
Oder kennt jemand noch einen anderen Algorithmus zum finden des n-kleinsten Elementes, der eine hier nicht genannte Eigenschaft des Heaps ausnutzt ?
a+
Hartmut
Hallo Felix,
man kann bei geschickter Wahl den Heap so aufbauen, dass es in
O(1) möglich ist das kleinste Element zu finden.
(Heapstruktur Minimum ist die Wurzel) jedoch benötigt man zur Reorganisation des Heaps O(log(n)) (nach löschen des Minimums)
Also benötigt man O(k*log(n)) für das k-kleinste Element zu finden. Auch bei einem d-Heap ist dies nicht möglich.
O(d*logd(n)) pro Reorganisationsschritt.
Also kann man die Frage mit Nein beantworten.
Gruss Peter
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]