LLD-Datenstrukturen im Designkontext: Die Heap-Eigenschaft - die einfache Regel, die Heaps mächtig macht

"Ein Heap bleibt nicht nützlich, weil alles sortiert ist." Es bleibt nützlich, weil jeder Elternteil einer einfachen Regel folgt. Im vorherigen Artikel haben wir gelernt, dass ein Heap für kontinuierliche Entscheidungsfindung gebaut wird. Ob es darum geht, den nächsten Fahrer zuzuweisen, den nächsten Prozess zu planen oder das dringendste Support-Ticket auszuwählen, das System braucht immer eines: Aber das wirft eine interessante Frage auf. Wie kann ein Heap immer den besten Kandidaten kennen, ohne alles zu sortieren? Die Antwort liegt in einer einfachen Regel: The Heap Property. Diese einzige Regel gibt einem Heap seine Macht. Das größte Missverständnis über Heaps Viele Anfänger stellen sich einen solchen Heap vor. Alles perfekt sortiert. Es fühlt sich logisch an. Wenn das größte Element immer an erster Stelle stehen sollte, sollte nicht jedes Element in Ordnung gebracht werden? Überraschenderweise nein. Ein Heap löst ein viel kleineres Problem. Es garantiert nur, dass das beste Element immer leicht zu erreichen ist. Alles andere muss nur einer einfachen Beziehung folgen. Stellen Sie sich eine Firmenhierarchie vor Denken Sie an die Struktur eines Unternehmens. Der CEO verwaltet nicht direkt jeden Mitarbeiter. Stattdessen ist jeder Manager nur für die Menschen direkt unter ihnen verantwortlich. Die gesamte Organisation funktioniert, weil jeder Manager seine lokale Verantwortung erfüllt. Ein Heap funktioniert auf sehr ähnliche Weise. Jeder Knoten muss nur die richtige Beziehung zu seinen unmittelbaren Kindern aufrechterhalten. Es muss nicht über jeden anderen Knoten in der Struktur Bescheid wissen. Die Heap-Eigenschaft Schauen wir uns einen Max Heap an. Beachten Sie das Muster. Jeder Elternteil hat einen Wert, der größer oder gleich seinen Kindern ist. Das ist die Heap-Eigenschaft. Das ist es. Es gibt keine Regel, die besagt, dass jeder Knoten größer sein muss als jeder andere Knoten im Heap. Nur die Eltern-Kind-Beziehung zählt. Was ist mit einem Min Heap? Einige Systeme wollen zuerst den kleinsten Wert. Zum Beispiel: früheste Frist niedrigste Antwortzeit Günstigste Versandoption In diesen Fällen kehrt sich die Regel einfach um. Beispiel: Auch hier ist die gesamte Struktur nicht sortiert. am