Cele mai mici elemente

de Mihai Scorțaru · 20 iunie 2015

Destul de des în practică apare următoarea problemă: alegeți cele mai mici k elemente dintr-o colecție. În funcție de situație avem diverse tipuri de colecții și diverse semnificații pentru noțiunea de mai mic. În cadrul acestui articol vom lucra cu numere întregi și vom utiliza ordinea obișnuită. Așadar, problema noastră devine: alegeți cele mai mici k numere dintr-un vector cu n numere.

Vom folosi limbajul C++ și vom scrie o funcție care are ca parametri un vector de numere întregi și un număr k; vom returna un alt vector. Vom prezenta mai multe soluții; în general nu ne interesează dacă vectorul inițial este modificat și nici dacă rezultatul este sau nu sortat. Pentru fiecare soluție vom preciza dacă are vreuna dintre aceste caracteristici.

Prima soluție

Soluția cea mai la îndemână ar fi să determinăm cea mai mică valoare, să o eliminăm din vector, să determinăm din nou cea mai mică valoare, să o eliminăm și pe ea și să continuăm în acest fel până ajungem la k elemente.
Observăm că vectorul original este nemodificat, iar rezultatul este sortat. Ordinul de complexitate al algoritmului este O(nk).

Bubble Sort

Cea de-a doua soluție este inspirată din bubble sort. În varianta standard, acest algoritm de sortare are următoarea caracteristică: la fiecare iterație a buclei exterioare, cel puțin un element ajunge pe poziția sa corectă, iar unul dintre elementele care ajunge în poziția corectă se mută "în spate", imediat înainte de ultimele elemente care sunt deja sortate. Dar, dacă inversăm ordinea în care parcurgem elementele în bucla interioară obținem efectul invers: elementele sortate sunt la început. Așadar, după prima iterație știm sigur că cel mai mic element se află pe prima poziție a vectorului, după a doua iterație știm sigur că al doilea cel mai mic element se află pe a doua poziție a șirului etc. Așadar, după cel mult k iterații, cele mai mici k elemente se vor afla la locul lor; ca urmare, nu trebuie să executăm întregul algoritm de sortare; ne putem opri după k iterații.
Vectorul original este modificat, dar rezultatul este sortat. Ordinul de complexitate al algoritmului este O(nk). Nu e mult mai bine, dar e puțin altfel... Soluția poate fi extinsă și pentru alți algoritmi de sortare care garantează că după k iterații cele mai mici k elemente ajung pe pozițiile lor finale în șirul sortat. Un astfel de algoritm este selection sort.

Sortare eficientă

Pasul următor nu este greu de găsit. Putem sorta șirul mai eficient și apoi alege primele k elemente.
Vectorul original este modificat și de data aceasta, iar rezultatul este sortat. Ordinul de complexitate este O(nlogn). E mai rapid dacă valoarea k este mare; pentru valori mici (logaritmice relativ la n) versiunile anterioare sunt mai performante.

Pas cu pas

Ne putem imagina un algoritm similar celui care determina minimul unui șir, dar în loc să determinăm un singur minim, am dori să determinăm k. În cazul minimului consideram că acesta este primul element și apoi parcurgeam vectorul; dacă un element era mai mic decât minimul curent, actualizam minimul. Putem porni cu primele k elemente; vom considera că acestea sunt minimele. Parcurgem vectorul și dacă un element este mai mic decât unul dintre cele k (comparăm doar cu cel mai mare dintre cele k minime), atunci îl includem în lista minimelor și îl eliminăm pe cel care a fost cel mai mare în acea listă. Va trebui să determinăm apoi care este noul maxim al minimelor.
Vectorul inițial nu este modificat, dar rezultatul nu este sortat. Ordinul de complexitate al algoritmului este O(k(n - k)).

Min-heap

Putem încerca să îmbunătățim prima variantă. Trebuie să extragem minimul de k ori. Putem folosi o structură de date care ne permite să realizăm eficient această operație: un min-heap. Transformăm vectorul într-un heap și extragem minimul de k ori.

Dacă heap-ul este creat peste vector (fără a se realiza o copie), atunci vectorul este modificat. Rezultatul este sortat. Ordinul de complexitate este O(n + klogn).

Max-heap

Putem folosi un heap și pentru a îmbunătăți varianta care încearcă să determine deodată cele k minime. Dacă am folosi un max-heap pentru a păstra aceste minime, atunci ne-ar fi mult mai ușor să determinăm maximul lor și să efectuăm verificările.
Dacă heap-ul este create peste primele k elemente ale vectorului, atunci acesta este modificat (nici măcar nu va mai conține aceleași valori, fiindcă pe măsură ce se execută algoritmul, elemente aflate în ultimele n - k poziții pot intra în heap și valorile pe care le înlocuiesc se pierd). Interesant este faptul că, fiindcă folosim un max-heap, rezultatul este sortat descrescător. Ordinul de complexitate al algoritmului este O(k + (n - k)logk).

Statistici de ordine

Să încercăm o abordare diferită. Dacă am ști care este al k-lea element ca mărime al șirului, am putea apoi să parcurgem șirul și să extragem elementele mai mici sau egale cu el. Va trebui să fim atenți dacă sunt mai multe valori egale cu elementul determinat și să includem prea multe sau prea puține în rezultat. Problema este foarte ușor de rezolvat dacă realizăm o partiționare de tip quicksort în jurul acestui al k-lea element.

Vectorul original este modificat (dacă nu creăm o copie), rezultatul nu este sortat, dar ordinul de complexitate al algoritmului este O(n).

Note

Pentru implementări am folosit din plin facilitățile oferite de librăria STL. Soluțiile C++ sunt simple și elegante. Dacă am folosi alte limbaje, codul ar fi fost mai complicat, dar conceptele ar fi fost aceleași.

În cadrul articolului am încercat să nu ne referim la implementarea propriu-zisă. De exemplu, am spus că în cazul folosirii unor heap-uri puteam sau nu să construim copii. Implementările prezentate construiesc astfel de copii, dar este doar un detaliu de implementare.