Curs Sortarea

Reamintim ca la sortarea prin selectie directa aveam de selectat la fiecare pas i, minimul din vectorul A[i..n]. Cautarea minimului se facea secvential, deci numarul de comparatii era tot timpul maxim, independent de ordinea initiala a cheilor si egal cu lungimea vectorului.

Sortarea prin selectie s-ar putea imbunatati daca am avea o structura de date de pe care extragerea minimului (respectiv a maximului) sa se faca rapid, daca se poate chiar optim. inca nu stim ce inseamna optim, dar vom vedea ca va fi de ordinul O(log2n). Introducem in aceasta sectiune o structura arborescenta care optimizeaza operatia de extragere a  maximului, si anume arborele partial ordonat si complet, adica ansamblul.