Heap: Speicherzuweisung oder Datenstruktur? Eine Geschichte aus zwei Begriffen.

Heap: Ein zweischneidiger Begriff in der Informatik

Der Begriff „Heap“ kommt in der Informatik zweimal vor und repräsentiert unterschiedliche Konzepte, die möglicherweise auftreten Lassen Sie einige verwirrt zurück. Ein Konzept bezieht sich auf den Laufzeitheap, der für die dynamische Speicherzuweisung in Sprachen im C-Stil verwendet wird, während das andere eine spezifische Datenstruktur bezeichnet, die für Prioritätswarteschlangen verwendet wird. Warum also diese Überschneidung in der Terminologie?

Der Laufzeitheap

Laut Donald Knuth in „The Art of Computer Programming“ wurde der Begriff „Heap“ erstmals verwendet um 1975 von verschiedenen Autoren zum Laufzeit-Heap hinzugefügt. Diese Verwendung entstand aus der Analogie zu einem physischen Heap, einem Stapel von Elementen, die hinzugefügt oder entfernt werden können Jeder Punkt. Im Kontext der Speicherverwaltung fungiert der Laufzeit-Heap als Pool verfügbaren Speichers, in dem eine dynamische Speicherzuweisung erfolgt.

Priority Queue Heaps

Getrennt davon wird der Begriff „Heap“ verwendet „ wurde verwendet, um eine Datenstruktur zu beschreiben, die Elemente basierend auf einem Schlüssel in einem teilweise geordneten Binärbaum organisiert. Diese Datenstruktur ist besonders nützlich für die Implementierung von Prioritätswarteschlangen, bei denen das Element mit der höchsten (oder niedrigsten) Priorität in konstanter Zeit abgerufen werden kann.

Gibt es eine Verbindung?

Trotz der gemeinsamen Nomenklatur besteht keine direkte Beziehung zwischen dem Laufzeit-Heap und den Prioritätswarteschlangen-Heaps. Ersteres ist ein Konzept im Zusammenhang mit der Speicherzuweisung und -verwaltung, während letzteres eine Datenstruktur mit einer bestimmten Struktur und Eigenschaften ist.

Das obige ist der detaillierte Inhalt vonHeap: Speicherzuweisung oder Datenstruktur? Eine Geschichte aus zwei Begriffen.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!