De ce contează?
O structură de date e ca o trusă de scule. Un cuțit elvețian face de toate, dar fiecare lucru îl face mediocru; un set de chei fixe e perfect, dar doar pentru piulițe. Nu există sculă universală — există sculă potrivită pentru sarcină. Tot așa, nu alegi structura după cum „arată” problema, ci după operațiile pe care le repeți de un milion de ori.
Ce este
O structură de date nu e doar un loc unde ții niște numere — e un contract de operații, fiecare cu un preț. Aceleași date pot sta într-un vector, într-o listă, într-un arbore de căutare sau într-un heap; ce diferă enorm e cât costă fiecare operație. Aproape orice problemă se reduce la cinci operații elementare:
- CĂUTARE — „există valoarea
x?” - INSERARE — adaugi o valoare nouă.
- ȘTERGERE — scoți o valoare existentă.
- MIN / MAX — „care e cel mai mic / cel mai mare element acum?”
- SUCCESOR — „care e cea mai mică valoare strict mai mare decât
x?” (fratele lui: predecesorul).
Imaginea mentală: fiecare structură e un meniu cu prețuri pentru aceste cinci operații. Întrebarea corectă nu este „unde îmi pun datele?”, ci „ce fac cu ele cel mai des, și care meniu face acel lucru ieftin?”.
Nicio structură nu câștigă la toate — fiecare O(1) sau O(log n) se plătește
altundeva. Vectorul sortat caută în O(log n), dar plătește O(n) la fiecare
inserare; heap-ul îți dă maximul în O(1), dar renunță la căutarea rapidă. De
aceea, citește operațiile din enunț întâi, și abia apoi alege structura.