Wann würde ich einen Haufen verwenden wollen?

Wann wäre neben der offensichtlichen Antwort einer Priority Queue ein Haufen für meine Programmierabenteuer nützlich?

Verwenden Sie es immer dann, wenn Sie schnellen Zugriff auf das größte (oder kleinste) Element benötigen, da dieses Element immer das erste Element im Array oder im Stammverzeichnis des Baums ist.

Der Rest des Arrays bleibt jedoch teilweise unsortiert. Somit ist ein sofortiger Zugriff nur auf das größte (kleinste) Objekt möglich. Das Einfügen ist schnell, daher ist es eine gute Möglichkeit, mit eingehenden Ereignissen oder Daten umzugehen und immer Zugriff auf die frühesten / größten zu haben.

Nützlich für Prioritätswarteschlangen, Scheduler (wo das früheste Element gewünscht wird) usw.

Ein Heap ist ein Baum, in dem der Wert eines übergeordneten Knotens größer ist als der eines seiner untergeordneten Knoten.

Wenn Sie sich einen Heap als einen Binärbaum vorstellen, der in linearer Reihenfolge nach Tiefe gespeichert ist, wobei zuerst der Wurzelknoten (dann die Kinder dieses Knotens, dann die Kinder dieser Knoten als nächstes); dann sind die Kinder eines Knotens am Index N bei 2N + 1 und 2N + 2. Diese Eigenschaft ermöglicht einen schnellen Zugriff nach Index. Und da Heaps durch Vertauschen von Knoten manipuliert werden, ermöglicht dies eine direkte Sortierung.

Haufen sind Strukturen, die einen schnellen Zugriff auf die Min- oder Max-Werte ermöglichen .

Aber warum willst du das? Sie können einfach jeden Eintrag beim Hinzufügen überprüfen, um festzustellen , ob er der kleinste oder der größte ist. Auf diese Weise haben Sie immer den kleinsten oder den größten in konstanter Zeit O(1).

Die Antwort liegt darin, dass Sie mit Haufen die kleinsten oder größten ziehen und schnell die nächsten kleinsten oder größten erkennen können . Aus diesem Grund wird es als Priority Queue bezeichnet.

Beispiel aus der realen Welt (allerdings keine sehr faire Welt):

Angenommen, Sie haben ein Krankenhaus, in dem Patienten je nach Alter betreut werden. Die ältesten werden immer zuerst besucht, egal wann sie in der Warteschlange stehen.

Sie können nicht einfach den ältesten verfolgen, denn wenn Sie ihn herausziehen, kennen Sie den nächstältesten nicht. Um dieses Krankenhausproblem zu lösen, implementieren Sie einen maximalen Heap . Dieser Haufen ist per Definition teilweise geordnet. Dies bedeutet, dass Sie die Patienten nicht nach ihrem Alter sortieren können, aber Sie wissen, dass die ältesten immer oben sind, sodass Sie einen Patienten in konstanter Zeit herausziehen O(1)und den Haufen in der Protokollzeit neu ausgleichen können O(log N).

Anspruchsvolleres Beispiel:

Angenommen, Sie haben eine Folge von ganzen Zahlen und möchten die verfolgen median. Der Median ist die Zahl, die sich in der Mitte eines geordneten Arrays befindet.

Beispiel:

[1, 2, 5, 7, 23, 27, 31]

Im obigen Fall 7ist der Median, weil das Array mit den kleineren Zahlen [1, 2, 5]dieselbe Größe hat wie das Array mit den größeren Zahlen [23, 27, 31]. Wenn das Array eine ungerade Anzahl von Elementen hat, ist der Median normalerweise der arithmetische Durchschnitt der 2 Elemente in der Mitte, z (5 + 7)/2.

Wie verfolgen Sie nun den Median? Bei 2 Heaps enthält ein Min-Heap die Zahlen, die kleiner als der aktuelle Median sind, und ein Max-Heap die Zahlen, die größer als der aktuelle Median sind. Wenn diese Heaps immer ausgeglichen sind, enthalten die 2 Heaps die gleiche Anzahl von Elementen, oder einer hat 1 Element mehr als der andere, am meisten.

Wenn Sie der Sequenz ein neues Element hinzufügen und die Zahl kleiner als der aktuelle Median ist, fügen Sie es dem Min-Heap hinzu, andernfalls fügen Sie es dem Max-Heap hinzu. Wenn die Heaps nicht ausgeglichen sind (ein Heap hat mehr als 1 Element mehr als der andere), ziehen Sie ein Element aus dem größten Heap und fügen es dem kleinsten hinzu. Jetzt sind sie ausgeglichen.

Das Merkmal eines Heaps ist, dass es sich um eine Struktur handelt, die Daten vorbestellt. Daher ist es ein guter Kompromiss zwischen den Kosten für die Aufrechterhaltung einer vollständigen Bestellung und den Kosten für die Suche durch zufälliges Chaos. Diese Eigenschaft wird bei vielen Algorithmen verwendet, z. B. Auswahl, Reihenfolge oder Klassifizierung.

Ein weiteres nützliches Merkmal eines Heaps ist, dass er direkt aus einem Array erstellt werden kann!

Auch gut für Auswahlalgorithmen (Finden der Min oder Max)

Wenn Sie eine temporäre Liste sortieren, sollten Sie immer Haufen in Betracht ziehen.

Sie können minHeap oder maxHeap verwenden, wenn Sie auf die kleinsten bzw. größten Elemente zugreifen möchten.