Heap (Datenstruktur) - Versionsgeschichte

141.30.244.84: Redundanz

2025-05-12T22:44:23Z

Redundanz

← Nächstältere Version		Version vom 13. Mai 2025, 00:44 Uhr
Zeile 1:		Zeile 1:
			{{Redundanztext
			\|3=Binärer Heap
			\|4=Heap (Datenstruktur)
			\|2=Mai 2025\|1=[[Spezial:Beiträge/141.30.244.84\|141.30.244.84]] 00:43, 13. Mai 2025 (CEST)}}
	[[Datei:Min-heap-1.svg\|mini\|hochkant=1.7\|Beispiel eines Min-Heaps]]		[[Datei:Min-heap-1.svg\|mini\|hochkant=1.7\|Beispiel eines Min-Heaps]]
	Ein '''{{lang\|en\|Heap}}''' (englisch wörtlich: ''Haufen'' oder ''Halde'') in der [[Informatik]] ist eine zumeist auf [[Baum (Graphentheorie)\|Bäumen]] basierende [[Abstrakter Datentyp\|abstrakte]] [[Datenstruktur]]. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung von [[Menge (Mathematik)\|Mengen]]. Den Elementen ist dabei ein [[Nummerung\|Schlüssel]] zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet.		Ein '''{{lang\|en\|Heap}}''' (englisch wörtlich: ''Haufen'' oder ''Halde'') in der [[Informatik]] ist eine zumeist auf [[Baum (Graphentheorie)\|Bäumen]] basierende [[Abstrakter Datentyp\|abstrakte]] [[Datenstruktur]]. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung von [[Menge (Mathematik)\|Mengen]]. Den Elementen ist dabei ein [[Nummerung\|Schlüssel]] zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet.

2A02:8071:5620:17C0:4CB1:52CB:83F9:9455: Beispielcode sollte kein Memoryleak enthalten

2024-10-26T16:20:32Z

Beispielcode sollte kein Memoryleak enthalten

← Nächstältere Version		Version vom 26. Oktober 2024, 18:20 Uhr
Zeile 67:		Zeile 67:
	public:		public:
	MinHeap(int);		MinHeap(int);
			~MinHeap();
	void MinHeapify(int);		void MinHeapify(int);
	int getParent(int index) { return (index - 1) / 2; }		int getParent(int index) { return (index - 1) / 2; }
Zeile 83:		Zeile 84:
	capacity = capacity;		capacity = capacity;
	elements = new int[capacity];		elements = new int[capacity];
			}

			MinHeap::~MinHeap() // Destruktor
			{
			delete[] elements;
	}		}

2A02:3100:15E4:B900:BD2D:B068:25E3:3AB3: /* Implementierung */

2024-03-16T10:05:41Z

Implementierung

← Nächstältere Version		Version vom 16. März 2024, 12:05 Uhr
Zeile 45:		Zeile 45:
	== Implementierung ==		== Implementierung ==
	[[Datei:Heap-as-array.svg\|mini\|Beispiel eines vollständigen binären Max-Heaps, der in einem [[Feld (Datentyp)\|Feld]] (Array) gespeichert wird.]]		[[Datei:Heap-as-array.svg\|mini\|Beispiel eines vollständigen binären Max-Heaps, der in einem [[Feld (Datentyp)\|Feld]] (Array) gespeichert wird.]]
	Heaps werden normalerweise mit einer impliziten Heap-Datenstruktur implementiert, bei der es sich um eine implizite [[Datenstruktur]] handelt, die aus einem [[Feld (Datentyp)\|Feld]] (Array) fester Größe oder einem dynamischen Array besteht, wobei jedes Element den Knoten eines Baums darstellt, dessen ~~Vater~~-Kind-Relation implizit durch seinen Index definiert wird. Nachdem ein Element in einen Heap eingefügt oder aus einem Heap gelöscht wurde, kann die Heap-Eigenschaft verletzt werden und der Heap muss durch Austauschen von Elementen innerhalb des Arrays ausgeglichen werden.		Heaps werden normalerweise mit einer impliziten Heap-Datenstruktur implementiert, bei der es sich um eine implizite [[Datenstruktur]] handelt, die aus einem [[Feld (Datentyp)\|Feld]] (Array) fester Größe oder einem dynamischen Array besteht, wobei jedes Element den Knoten eines Baums darstellt, dessen Eltern-Kind-Relation implizit durch seinen Index definiert wird. Nachdem ein Element in einen Heap eingefügt oder aus einem Heap gelöscht wurde, kann die Heap-Eigenschaft verletzt werden und der Heap muss durch Austauschen von Elementen innerhalb des Arrays ausgeglichen werden.

	In einer impliziten Heap-Datenstruktur enthält das erste oder letzte Element die [[Wurzel (Graphentheorie)\|Wurzel]]. Die nächsten beiden Elemente des Arrays enthalten seine untergeordneten Elemente. Die nächsten vier Elemente enthalten die vier Kinder der beiden Kindknoten usw. Somit würden sich die Kinder des Knotens an Position n an den Positionen ''2n'' und ''2n + 1'' in einem Array mit Startindex 1 oder an den Positionen ''2n + 1'' und ''2n + 2'' in einem Array mit Startindex 0 befinden. Die Berechnung des Index des übergeordneten Knotens des Elements an Position n ist ebenfalls unkompliziert. Bei einem Array mit Startindex 1 befindet sich das übergeordnete Element an Position ''n / 2''. Bei einem Array mit Startindex 0 das übergeordnete Element an der Position ''(n - 1) / 2''. Dies ermöglicht das Durchlaufen des [[Baum (Datenstruktur)\|Baums]] durch einfache Indexberechnungen. Das Ausbalancieren eines Heaps erfolgt durch Austauschen von Elementen, die nicht in Ordnung sind. Da wir einen Heap aus einem Array erstellen können, ohne zusätzlichen Speicher zu benötigen, kann [[Heapsort]] verwendet werden, um ein Array [[in-place]] zu sortieren.		In einer impliziten Heap-Datenstruktur enthält das erste oder letzte Element die [[Wurzel (Graphentheorie)\|Wurzel]]. Die nächsten beiden Elemente des Arrays enthalten seine untergeordneten Elemente. Die nächsten vier Elemente enthalten die vier Kinder der beiden Kindknoten usw. Somit würden sich die Kinder des Knotens an Position n an den Positionen ''2n'' und ''2n + 1'' in einem Array mit Startindex 1 oder an den Positionen ''2n + 1'' und ''2n + 2'' in einem Array mit Startindex 0 befinden. Die Berechnung des Index des übergeordneten Knotens des Elements an Position n ist ebenfalls unkompliziert. Bei einem Array mit Startindex 1 befindet sich das übergeordnete Element an Position ''n / 2''. Bei einem Array mit Startindex 0 das übergeordnete Element an der Position ''(n - 1) / 2''. Dies ermöglicht das Durchlaufen des [[Baum (Datenstruktur)\|Baums]] durch einfache Indexberechnungen. Das Ausbalancieren eines Heaps erfolgt durch Austauschen von Elementen, die nicht in Ordnung sind. Da wir einen Heap aus einem Array erstellen können, ohne zusätzlichen Speicher zu benötigen, kann [[Heapsort]] verwendet werden, um ein Array [[in-place]] zu sortieren.

2A02:3100:15E4:B900:BD2D:B068:25E3:3AB3: /* Heap-Bedingung */

2024-03-16T10:04:04Z

Heap-Bedingung

← Nächstältere Version		Version vom 16. März 2024, 12:04 Uhr
Zeile 33:		Zeile 33:

	== Heap-Bedingung ==		== Heap-Bedingung ==
	Man unterscheidet Heaps in Min-Heaps und Max-Heaps. Bei ''Min-Heaps'' bezeichnet man die Eigenschaft, dass die Schlüssel der Kinder eines Knotens stets größer als oder gleich dem Schlüssel ihres ~~Vaters~~ sind, als ''Heap-Bedingung''. Dies bewirkt, dass an der Wurzel des Baumes stets ein Element mit minimalem Schlüssel im Baum zu finden ist. Umgekehrt verlangt die Heap-Bedingung bei ''Max-Heaps'', dass die Schlüssel der Kinder eines Knotens stets kleiner als oder gleich die ihres ~~Vaters~~ sind. Hier befindet sich an der Wurzel des Baumes immer ein Element mit maximalem Schlüssel.		Man unterscheidet Heaps in Min-Heaps und Max-Heaps. Bei ''Min-Heaps'' bezeichnet man die Eigenschaft, dass die Schlüssel der Kinder eines Knotens stets größer als oder gleich dem Schlüssel ihres Elternknoten sind, als ''Heap-Bedingung''. Dies bewirkt, dass an der Wurzel des Baumes stets ein Element mit minimalem Schlüssel im Baum zu finden ist. Umgekehrt verlangt die Heap-Bedingung bei ''Max-Heaps'', dass die Schlüssel der Kinder eines Knotens stets kleiner als oder gleich die ihres Elternknoten sind. Hier befindet sich an der Wurzel des Baumes immer ein Element mit maximalem Schlüssel.

	Mathematisch besteht der Unterschied zwischen beiden Varianten nur in ihrer gegensätzlichen [[Ordnungsrelation\|Ordnung]] der Elemente. Da die Definition von ''auf-'' und ''absteigend'' rein willkürlich ist, ist es also eine Auslegungsfrage, ob es sich bei einer konkreten Implementierung um einen Min-Heap oder um einen Max-Heap handelt.		Mathematisch besteht der Unterschied zwischen beiden Varianten nur in ihrer gegensätzlichen [[Ordnungsrelation\|Ordnung]] der Elemente. Da die Definition von ''auf-'' und ''absteigend'' rein willkürlich ist, ist es also eine Auslegungsfrage, ob es sich bei einer konkreten Implementierung um einen Min-Heap oder um einen Max-Heap handelt.

2A00:20:304A:56D2:D2EA:A561:9BEC:84CE: /* Extract Min oder Extract Max */

2022-05-16T13:28:03Z

Extract Min oder Extract Max

← Nächstältere Version		Version vom 16. Mai 2022, 15:28 Uhr
Zeile 28:		Zeile 28:

	=== Extract Min oder Extract Max ===		=== Extract Min oder Extract Max ===
	~~Dieser~~ Operation gibt das maximale Element im Max-Heap oder das minimale Element im Min-Heap zurück. Dieses Element ist die Wurzel des Heaps.		Diese Operation gibt das maximale Element im Max-Heap oder das minimale Element im Min-Heap zurück. Dieses Element ist die Wurzel des Heaps.

	Daneben werden häufig auch die [[Operation (Informatik)\|Operationen]] ''changeKey'' zum Anpassen des Schlüssels und ''merge'' zum Verschmelzen zweier Heaps bereitgestellt. Die Operation ''changeKey'' wird häufig durch die Nacheinanderausführung der Operationen ''remove'' und ''insert'' gebildet, wobei nach dem Entfernen und vor dem erneuten Einfügen der Schlüssel angepasst wird. In einigen Fällen bieten Heaps statt ''changeKey'' lediglich die Operation ''decreaseKey'' an, bei der der Schlüssel lediglich verkleinert werden darf.		Daneben werden häufig auch die [[Operation (Informatik)\|Operationen]] ''changeKey'' zum Anpassen des Schlüssels und ''merge'' zum Verschmelzen zweier Heaps bereitgestellt. Die Operation ''changeKey'' wird häufig durch die Nacheinanderausführung der Operationen ''remove'' und ''insert'' gebildet, wobei nach dem Entfernen und vor dem erneuten Einfügen der Schlüssel angepasst wird. In einigen Fällen bieten Heaps statt ''changeKey'' lediglich die Operation ''decreaseKey'' an, bei der der Schlüssel lediglich verkleinert werden darf.

Trustable: Siehe-auch-Eintrag entfernt, da bereits oben verlinkt

2022-01-06T15:40:14Z

Siehe-auch-Eintrag entfernt, da bereits oben verlinkt

← Nächstältere Version		Version vom 6. Januar 2022, 17:40 Uhr
Zeile 4:		Zeile 4:
	Über die Menge der Schlüssel muss daher eine totale [[Ordnungsrelation\|Ordnung]] festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird. Beispielsweise könnte die Menge der [[Ganze Zahl\|ganzen Zahlen]] zusammen mit dem [[Vergleichsoperator]] < als Schlüsselmenge fungieren.		Über die Menge der Schlüssel muss daher eine totale [[Ordnungsrelation\|Ordnung]] festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird. Beispielsweise könnte die Menge der [[Ganze Zahl\|ganzen Zahlen]] zusammen mit dem [[Vergleichsoperator]] < als Schlüsselmenge fungieren.

	Der Begriff Heap wird häufig als bedeutungsgleich zu einem [[Binärbaum#Partiell geordneter Baum\|partiell geordneten Baum]] verstanden (siehe Abbildung). Gelegentlich versteht man einschränkend nur eine besondere Implementierungsform eines partiell geordneten Baums, nämlich die Einbettung in ein [[Feld (Datentyp)\|~~Array~~]], als Heap.		Der Begriff Heap wird häufig als bedeutungsgleich zu einem [[Binärbaum#Partiell geordneter Baum\|partiell geordneten Baum]] verstanden (siehe Abbildung). Gelegentlich versteht man einschränkend nur eine besondere Implementierungsform eines partiell geordneten Baums, nämlich die Einbettung in ein [[Feld (Datentyp)\|Feld]] (Array), als Heap.

	Verwendung finden Heaps vor allem dort, wo es darauf ankommt, schnell ein Element mit höchster Priorität aus dem Heap zu entnehmen ([[Highest In – First Out\|HIFO-Prinzip]]), beispielsweise bei [[Vorrangwarteschlange]]n.		Verwendung finden Heaps vor allem dort, wo es darauf ankommt, schnell ein Element mit höchster Priorität aus dem Heap zu entnehmen ([[Highest In – First Out\|HIFO-Prinzip]]), beispielsweise bei [[Vorrangwarteschlange]]n.
Zeile 44:		Zeile 44:

	== Implementierung ==		== Implementierung ==
	[[Datei:Heap-as-array.svg\|mini\|Beispiel eines vollständigen binären Max-Heaps, der in einem [[Feld (Datentyp)\|~~Array~~]] gespeichert wird.]]		[[Datei:Heap-as-array.svg\|mini\|Beispiel eines vollständigen binären Max-Heaps, der in einem [[Feld (Datentyp)\|Feld]] (Array) gespeichert wird.]]
	Heaps werden normalerweise mit einer impliziten Heap-Datenstruktur implementiert, bei der es sich um eine implizite [[Datenstruktur]] handelt, die aus einem [[Feld (Datentyp)\|~~Array~~]] fester Größe oder einem dynamischen Array besteht, wobei jedes Element den Knoten eines Baums darstellt, dessen Vater-Kind-Relation implizit durch seinen Index definiert wird. Nachdem ein Element in einen Heap eingefügt oder aus einem Heap gelöscht wurde, kann die Heap-Eigenschaft verletzt werden und der Heap muss durch Austauschen von Elementen innerhalb des Arrays ausgeglichen werden.		Heaps werden normalerweise mit einer impliziten Heap-Datenstruktur implementiert, bei der es sich um eine implizite [[Datenstruktur]] handelt, die aus einem [[Feld (Datentyp)\|Feld]] (Array) fester Größe oder einem dynamischen Array besteht, wobei jedes Element den Knoten eines Baums darstellt, dessen Vater-Kind-Relation implizit durch seinen Index definiert wird. Nachdem ein Element in einen Heap eingefügt oder aus einem Heap gelöscht wurde, kann die Heap-Eigenschaft verletzt werden und der Heap muss durch Austauschen von Elementen innerhalb des Arrays ausgeglichen werden.

	In einer impliziten Heap-Datenstruktur enthält das erste oder letzte Element die [[Wurzel (Graphentheorie)\|Wurzel]]. Die nächsten beiden Elemente des Arrays enthalten seine untergeordneten Elemente. Die nächsten vier Elemente enthalten die vier Kinder der beiden Kindknoten usw. Somit würden sich die Kinder des Knotens an Position n an den Positionen ''2n'' und ''2n + 1'' in einem Array mit Startindex 1 oder an den Positionen ''2n + 1'' und ''2n + 2'' in einem Array mit Startindex 0 befinden. Die Berechnung des Index des übergeordneten Knotens des Elements an Position n ist ebenfalls unkompliziert. Bei einem Array mit Startindex 1 befindet sich das übergeordnete Element an Position ''n / 2''. Bei einem Array mit Startindex 0 das übergeordnete Element an der Position ''(n - 1) / 2''. Dies ermöglicht das Durchlaufen des [[Baum (Datenstruktur)\|Baums]] durch einfache Indexberechnungen. Das Ausbalancieren eines Heaps erfolgt durch Austauschen von Elementen, die nicht in Ordnung sind. Da wir einen Heap aus einem Array erstellen können, ohne zusätzlichen Speicher zu benötigen, kann [[Heapsort]] verwendet werden, um ein Array [[in-place]] zu sortieren.		In einer impliziten Heap-Datenstruktur enthält das erste oder letzte Element die [[Wurzel (Graphentheorie)\|Wurzel]]. Die nächsten beiden Elemente des Arrays enthalten seine untergeordneten Elemente. Die nächsten vier Elemente enthalten die vier Kinder der beiden Kindknoten usw. Somit würden sich die Kinder des Knotens an Position n an den Positionen ''2n'' und ''2n + 1'' in einem Array mit Startindex 1 oder an den Positionen ''2n + 1'' und ''2n + 2'' in einem Array mit Startindex 0 befinden. Die Berechnung des Index des übergeordneten Knotens des Elements an Position n ist ebenfalls unkompliziert. Bei einem Array mit Startindex 1 befindet sich das übergeordnete Element an Position ''n / 2''. Bei einem Array mit Startindex 0 das übergeordnete Element an der Position ''(n - 1) / 2''. Dies ermöglicht das Durchlaufen des [[Baum (Datenstruktur)\|Baums]] durch einfache Indexberechnungen. Das Ausbalancieren eines Heaps erfolgt durch Austauschen von Elementen, die nicht in Ordnung sind. Da wir einen Heap aus einem Array erstellen können, ohne zusätzlichen Speicher zu benötigen, kann [[Heapsort]] verwendet werden, um ein Array [[in-place]] zu sortieren.
Zeile 262:		Zeile 262:

	== Siehe auch ==		== Siehe auch ==
	* [[Heapsort]]
	* [[Feld (Datentyp)]]
	* [[Liste (Datenstruktur)]]		* [[Liste (Datenstruktur)]]
	* [[Menge (Datenstruktur)]]		* [[Menge (Datenstruktur)]]
	* [[Stapelspeicher]]		* [[Stapelspeicher]]
	* [[Warteschlange (Datenstruktur)]]

	== Literatur ==		== Literatur ==

Trustable: seltsamen HTML-Code im Wort entfernt

2022-01-06T15:38:33Z

seltsamen HTML-Code im Wort entfernt

← Nächstältere Version		Version vom 6. Januar 2022, 17:38 Uhr
Zeile 161:		Zeile 161:
	if (rightIndex != index)		if (rightIndex != index)
	{		{
	swap(&elements[index], &elements[rightIndex]); // Vertauscht das Wurzel-Element mit dem Wurzel-Element des rechten Teilbaums		swap(&elements[index], &elements[rightIndex]); // Vertauscht das Wurzel-Element mit dem Wurzel-Element des rechten Teilbaums
	MinHeapify(rightIndex); // Aufruf der rekursiven Methode für den rechten Teilbaum		MinHeapify(rightIndex); // Aufruf der rekursiven Methode für den rechten Teilbaum
	}		}
Zeile 196:		Zeile 196:

	=== Fibonacci-Heap ===		=== Fibonacci-Heap ===
	Ein [[Fibonacci-Heap]] ist ähnlich wie ein [[Binomial-Heap]] in einer [[Vorrangwarteschlange]] realisiert. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge [[Effizienz (Informatik)\|effizient]] im Heap gespeichert werden können und stets ein Element mit höchster Priorität entnommen werden kann. Die Priorität der Elemente wird diesen durch [[~~Schlüssel (Informatik)~~\|Schlüssel]] aufgeprägt. Über der Menge der Schlüssel muss daher eine [[Totalordnung]] bestehen, wie sie zum Beispiel die Kleiner-Gleich-Relation über den [[Ganze Zahl\|ganzen Zahlen]] darstellt.		Ein [[Fibonacci-Heap]] ist ähnlich wie ein [[Binomial-Heap]] in einer [[Vorrangwarteschlange]] realisiert. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge [[Effizienz (Informatik)\|effizient]] im Heap gespeichert werden können und stets ein Element mit höchster Priorität entnommen werden kann. Die Priorität der Elemente wird diesen durch [[Nummerung\|Schlüssel]] aufgeprägt. Über der Menge der Schlüssel muss daher eine [[Totalordnung]] bestehen, wie sie zum Beispiel die Kleiner-Gleich-Relation über den [[Ganze Zahl\|ganzen Zahlen]] darstellt.

	Weitere Varianten sind der [[Min-Max-Heap]], der [[Linksbaum]], der [[Treap]] und der [[Radix Heap\|Radix-Heap]].		Weitere Varianten sind der [[Min-Max-Heap]], der [[Linksbaum]], der [[Treap]] und der [[Radix Heap\|Radix-Heap]].
Zeile 218:		Zeile 218:
	! amortisiert		! amortisiert
	! amortisiert		! amortisiert
			! amortisiert !!
	! am<span class="tlid-translation-gender-indicator translation-gender-indicator"></span>ortisiert !!
	\|-		\|-
	\| extract-min		\| extract-min
Zeile 253:		Zeile 253:
	\|\| <math>\mathcal{O}(1)</math>		\|\| <math>\mathcal{O}(1)</math>
	\|\| <math>\mathcal{O}(\log n)</math> (<math>\mathcal{O}(1)</math> vermutet)		\|\| <math>\mathcal{O}(\log n)</math> (<math>\mathcal{O}(1)</math> vermutet)
	\|\| <math>\mathcal{O}(1)</math> oder <math>\mathcal{O}(\log n)</math> \|\|		\|\| <math>\mathcal{O}(1)</math> oder <math>\mathcal{O}(\log n)</math> \|\|
	\|}		\|}

	== Anwendung ==		== Anwendung ==
	Heaps haben ein breites Spektrum an Anwendungen. Häufig ist vor allem der Einsatz in [[Vorrangwarteschlange]]n, wie sie bei [[Server\|Servern]] oder [[Betriebssystem\|Betriebssystemen]] zur Festlegung der Ausführungsreihenfolge von Aufgaben ~~b<span class="tlid-translation-gender-indicator translation-gender-indicator"></span>enötigt~~ werden.		Heaps haben ein breites Spektrum an Anwendungen. Häufig ist vor allem der Einsatz in [[Vorrangwarteschlange]]n, wie sie bei [[Server\|Servern]] oder [[Betriebssystem\|Betriebssystemen]] zur Festlegung der Ausführungsreihenfolge von Aufgaben benötigt werden.

	Daneben gibt es aber auch Anwendungen, die nicht explizit den Einsatz von [[Warteschlange (Datenstruktur)\|Warteschlangen]] verlangen. Allgemein stellt ein Heap eine ideale [[Datenstruktur]] für [[Greedy-Algorithmus\|Greedy-Algorithmen]] dar, die schrittweise lokale optimierte Entscheidungen treffen. So wird zum Beispiel beim [[Sortierverfahren\|Sortieralgorithmus]] [[Heapsort]] ein [[Binärer Heap]] zum Sortieren eingesetzt. [[Fibonacci-Heap]]s finden beim [[Algorithmus von Dijkstra]] bzw. [[Algorithmus von Prim\|Prim]] Anwendung.		Daneben gibt es aber auch Anwendungen, die nicht explizit den Einsatz von [[Warteschlange (Datenstruktur)\|Warteschlangen]] verlangen. Allgemein stellt ein Heap eine ideale [[Datenstruktur]] für [[Greedy-Algorithmus\|Greedy-Algorithmen]] dar, die schrittweise lokale optimierte Entscheidungen treffen. So wird zum Beispiel beim [[Sortierverfahren\|Sortieralgorithmus]] [[Heapsort]] ein [[Binärer Heap]] zum Sortieren eingesetzt. [[Fibonacci-Heap]]s finden beim [[Algorithmus von Dijkstra]] bzw. [[Algorithmus von Prim\|Prim]] Anwendung.

87.142.223.196: /* Remove */

2021-12-14T08:43:53Z

Remove

← Nächstältere Version		Version vom 14. Dezember 2021, 10:43 Uhr
Zeile 22:		Zeile 22:

	=== Remove ===		=== Remove ===
	Das Entfernen eines Elements erfolgt, indem das ~~gelöscht~~ Element durch das letzte Element im Heap ersetzt wird. Dann wird das letzte Element aus dem Heap gelöscht. Nun wird das letzte Element an einer Stelle im Heap platziert. Es kann die Heap-Bedingung nicht erfüllen, sodass die Operation ''Down-Heapify'' durchgeführt wird, um die Eigenschaften des Heaps aufrechtzuerhalten.		Das Entfernen eines Elements erfolgt, indem das gelöschte Element durch das letzte Element im Heap ersetzt wird. Dann wird das letzte Element aus dem Heap gelöscht. Nun wird das letzte Element an einer Stelle im Heap platziert. Es kann die Heap-Bedingung nicht erfüllen, sodass die Operation ''Down-Heapify'' durchgeführt wird, um die Eigenschaften des Heaps aufrechtzuerhalten.

	=== Find-max oder Find-min ===		=== Find-max oder Find-min ===

Lynxbiru: /* Heapify */ Sprache korrigiert

2021-08-04T15:32:45Z

Heapify: Sprache korrigiert

← Nächstältere Version		Version vom 4. August 2021, 17:32 Uhr
Zeile 16:		Zeile 16:
	''Up-Heapify'' folgt dem Bottom-Up-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Wurzel geht, und wenn Knoten nicht die Heap-Bedingung erfüllen, werden bestimmte Operationen ausgeführt, damit der Baum der Heap-Bedingung folgt.		''Up-Heapify'' folgt dem Bottom-Up-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Wurzel geht, und wenn Knoten nicht die Heap-Bedingung erfüllen, werden bestimmte Operationen ausgeführt, damit der Baum der Heap-Bedingung folgt.

	''Down-Heapify'' folgt dem Top-Down-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Blätter geht, und ~~führt~~ bestimmte Operationen ~~ausgeführt~~, um die Heap-Bedingung herzustellen.		''Down-Heapify'' folgt dem Top-Down-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Blätter geht, und bestimmte Operationen ausführt, um die Heap-Bedingung herzustellen.

	=== Insert ===		=== Insert ===

Ruppscher: /* Operationen */

2021-07-23T20:12:04Z

Operationen

← Nächstältere Version		Version vom 23. Juli 2021, 22:12 Uhr
Zeile 16:		Zeile 16:
	''Up-Heapify'' folgt dem Bottom-Up-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Wurzel geht, und wenn Knoten nicht die Heap-Bedingung erfüllen, werden bestimmte Operationen ausgeführt, damit der Baum der Heap-Bedingung folgt.		''Up-Heapify'' folgt dem Bottom-Up-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Wurzel geht, und wenn Knoten nicht die Heap-Bedingung erfüllen, werden bestimmte Operationen ausgeführt, damit der Baum der Heap-Bedingung folgt.

	''Down-Heapify'' folgt dem Top-Down-Ansatz. In diesem Fall wird ~~prüfen wir~~, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Blätter geht, und führt bestimmte Operationen ausgeführt, um die Heap-Bedingung herzustellen.		''Down-Heapify'' folgt dem Top-Down-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Blätter geht, und führt bestimmte Operationen ausgeführt, um die Heap-Bedingung herzustellen.

	=== Insert ===		=== Insert ===