Heap

Datenstrukturen Heaps werden in min-heap und max-heap min-heap Eltern Knoten sind $\le$ Kinder, Wurzel ist kleinste Zahl max-heap Eltern Knoten sind $\ge$ Kinder, Wurzel ist größte Zahl

Wofür ist das gut

Sofortiger Zugriff auf Maximum/Minimum ⇒ O(1)

Einfügen Entfernen → $O(\log n)$

Access Heap

• Für Index i:

  • Left child = 2*i + 1

  • Right child = 2*i + 2

  • Parent = (i - 1) // 2