Hauger - Heaps

En Datastruktur som er nyttig for å kunne bruke Heapsort (max-heaps), og å lage effektive prioritetskøer (min-heaps).

Ulikt Binære søketrær, som har mindre elementer til venstre og større elementer til høyre for rotnoden, har hauger en struktur s.a alt er mindre enn rota (i min-heaps).

---

Forskjellige type hauger

min-heaps max-heaps

Støttefunksjoner for hauger

Left RIGHT Parent

NB: Dette er nummerering, ikke verdier Barna til node $i$ $2i$ og $2i+1$

Algoritmer som bruker hauger

Max-Heapify Build-Max-Heap Heapsort Max-Heap-Insert

---

Nødvendig for å implementere Prioritetskøer - Priority queues: Max-Heap-Extract-Max Max-Heap-Increase-Key Max-Heap-Maximum Max-Heap-Insert

Egenskaper

• Alltid balansert
• Så komplett/perfekt som strukturen tillater