Heap (Datenstruktur)
Ein Heap ist eine Baum-basierte Datenstruktur, die in diversen Algorithmen in der Informatik verwendet wird.
Ihre Basis-Datentypen müssen eine Ordnung besitzen. Es seien A und B Knoten eines Heap, wobei B ein Kind des Knoten A ist. Jeder Heap muss folgende Bedingung gewährleisten: Schlüssel(A) ≥ Schlüssel(B)
Dies ist die einzige Bedingung für generelle Heaps. Das bedeutet, dass der Größte (oder kleinste, je nach Vergleichssemantik) Schlüssel immer der Wurzel-Knoten ist.
Es existieren zahlreiche Heap-Varianten: