Ein Heap ist eine spezielle baumbasierte Datenstruktur, bei der der Baum ein vollständiger binärer Baum ist. Es gibt zwei Arten von Heaps: Min-Heap und Max-Heap. Ein Min-Heap wird verwendet, um auf das minimale Element im Heap zuzugreifen, während der Max-Heap verwendet wird, wenn auf das maximale Element im Heap zugegriffen wird.
In einem Min-Heap muss der Schlüssel, der am Wurzelknoten vorhanden ist, der kleinste unter den Schlüsseln sein, die bei allen seinen Kindern vorhanden sind. Dieselbe Eigenschaft muss für alle Teilbäume in diesem Binärbaum rekursiv wahr sein.
In einem Max-Heap muss der Schlüssel, der am Wurzelknoten vorhanden ist, der Größte unter den Schlüsseln sein, die bei allen seinen Kindern vorhanden sind. Dieselbe Eigenschaft muss für alle Teilbäume in diesem Binärbaum rekursiv wahr sein.
Lesen Sie auch: Unterschied zwischen Stack und Heap
Contents
Max Heap gegen Min Heap
| MAX. HAUFEN | MIN. HAUFEN |
| In einem Max-Heap muss der Schlüssel, der am Wurzelknoten vorhanden ist, größer oder gleich den Schlüsseln sein, die an allen seinen Kindern vorhanden sind. | In einem Min-Heap muss der am Wurzelknoten vorhandene Schlüssel kleiner oder gleich den Schlüsseln sein, die an allen seinen Kindern vorhanden sind. |
| Ein Max-Heap verwendet die absteigende Priorität. | Ein Min-Heap verwendet die aufsteigende Priorität. |
| In einem Max-Heap das maximale Schlüsselelement, das an der Wurzel vorhanden ist. | In einem Min-Heap das minimale Schlüsselelement, das an der Wurzel vorhanden ist. |
| In einem Max-Heap ist das größte Element das erste, das vom Haufen geholt wird. | In einem Min-Heap ist das kleinste Element das erste, das aus dem Haufen geholt wird. |
| Beim Bau eines Max-Heaps hat das größte Element Vorrang. | Beim Aufbau eines Min-Heaps hat das kleinste Element Vorrang. |
Lesen Sie auch: Unterschied zwischen Stapel- und Warteschlangendatenstrukturen
Was Sie über Min-Heap wissen müssen
- In einem Min-Heap muss der am Wurzelknoten vorhandene Schlüssel kleiner oder gleich den Schlüsseln sein, die an allen seinen Kindern vorhanden sind.
- Ein Min-Heap verwendet die aufsteigende Priorität.
- In einem Min-Heap das minimale Schlüsselelement, das an der Wurzel vorhanden ist.
- In einem Min-Heap ist das kleinste Element das erste, das aus dem Haufen geholt wird.
- Beim Aufbau eines Min-Heaps hat das kleinste Element Vorrang.
Was Sie über Max Heap wissen müssen
- In einem Max-Heap muss der Schlüssel, der am Wurzelknoten vorhanden ist, größer oder gleich den Schlüsseln sein, die an allen seinen Kindern vorhanden sind.
- Ein Max-Heap verwendet die absteigende Priorität.
- In einem Max-Heap das maximale Schlüsselelement, das an der Wurzel vorhanden ist.
- In einem Max-Heap ist das größte Element das erste, das vom Haufen geholt wird.
- Beim Bau eines Max-Heaps hat das größte Element Vorrang.
Fazit
Die Heap-Datenstruktur ist ein vollständiger Binärbaum, der die Heap-Eigenschaft erfüllt , wobei jeder gegebene Knoten ist:
- immer größer als sein Kindknoten und der Schlüssel des Wurzelknotens ist der größte unter allen anderen Knoten. Diese Eigenschaft wird auch als max heap bezeichnet .
- immer kleiner als der/die Kindknoten und der Schlüssel des Wurzelknotens ist der kleinste unter allen anderen Knoten. Diese Eigenschaft wird auch als min heap bezeichnet .