Fra Wikipedia, den frie encyklopædi
En hob (eng. heap) er en datastruktur, som findes i flere varianter. Det er en struktur, der garanterer, at dataelementet med den største nøgleværdi kan findes i konstant tid. I nogle sammenhænge bruger man en minimumshob, hvor det er det mindste element, der er hurtigt at få adgang til.
- En binær hob kan bruges i forbindelse med sortering af data
- En indekseret hob kan bruges til håndtering af dataelementer med variabel størrelse
Tidskompleksitet
| Operation |
Relativ tid |
| Find |
O(1) |
| Indsæt |
O(log2 N) |
| Slet |
O(log2 N) |
- Hob for andre betydninger.
