Cues de prioritat · 4.2
Heaps
Un arbre binari complet desat en un vector on cada pare és menor que els fills. Inserció i extracció en temps logarítmic.
Conceptes clau
- Arbre binari complet
- Propietat de heap
- Surar i enfonsar
- Representació en vector
Al vector, els fills de la posició i són a 2i+1 i 2i+2, i el pare a ⌊(i−1)/2⌋. Cada pare és més petit que els seus fills, així que el mínim és sempre a l'arrel.