Jak si vyberete správnou datovou strukturu pro problém?

Question

Accepted Answer

Vyberte strukturu, jejíž **nejčastěji používané operace jsou nejlevnější** pro váš přístupový vzor. Začněte vypsáním operací, které budete provádět, odhadněte jejich frekvenci a poté je přiřaďte k silným stránkám struktury.

## Kontrolní seznam rozhodování

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Přiřazení operací ke složitosti

| Potřeba | Nejlepší struktura | Cena klíčové operace |
|---|---|---|
| Náhodný přístup podle indexu | dynamic array | O(1) |
| Vyhledání podle klíče | hash map | O(1) avg |
| Seřazené + dotazy na rozsah | balanced BST | O(log n) |
| Min/max opakovaně | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Vyhledávání s předponou | trie | O(L) |

## Příklad uvažování

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Proč to je důležité

Správy volba je často rozdíl mezi řešením O(n) a O(n²) — největší páka na výkon.

Intervieweři testují právě toto uvažování: chtějí vidět, jak mapujete požadavky na náklady operací, ne jen memorování struktur.

Potřeba	Nejlepší struktura	Cena klíčové operace
Náhodný přístup podle indexu	dynamic array	O(1)
Vyhledání podle klíče	hash map	O(1) avg
Seřazené + dotazy na rozsah	balanced BST	O(log n)
Min/max opakovaně	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Vyhledávání s předponou	trie	O(L)