Datenstruktur zur Abspeicherung einer bzgl. einer binären Relation ≤ total geordneten Menge M.

Besteht M aus n Elementen, so ist der Heap ein gerichteter binärer Baum der Tiefe [log₂n]. Jedem Knoten v des Baumes ist ein Element φ((v) der Menge M zugeordnet und umgekehrt. Ein Heap erfüllt nach Definition die sog. Heap-Eigenschaft, daß für jede Kante (v, w) des gerichteten Baumes die Ungleichung \(\phi (v)\le \phi (w)\) gilt. Somit steht an der Wurzel des Baumes das kleinste Element der Menge M.

Löscht man die Wurzel des Baumes, so setzt man das einem tiefsten Blatt des Baumes zugeordnete Element von M an seine Stelle und läßt das Element so lange durch Vertauschen mit dem jeweils kleinsten der beiden Kinder nach unten sinken, bis die Heap-Eigenschaft wieder erfüllt ist.

Das Einfügen eines neuen Elementes in den Heap erfolgt entsprechend, indem an einer höchstliegenden möglichen Stelle im Baum ein Blatt mit dem neuen Element eingefügt wird und man dieses Element so lange durch Vertauschen mit dem Vaterknoten nach oben steigen läßt, bis die Heap- Eigenschaft wieder erfüllt ist.

Beide Operationen, Löschen des kleinsten Elementes aus dem Heap und Einfügen eines neuen Elementes in den Heap, benötigen höchstens c · [log₂n] Schritte für eine von n unabhängige Konstante c.

Heaps werden insbesondere im Rahmen von Heapsort angewendet.