Algoritmul HeapSort – Structuri si algoritmi de prelucrarea datelor - Tutunaru Sergiu

Extras din document

Este un algoritm, care a primit denumirea de aranjarea piramidala (HeapSort). Ideea sa, consta din: in loc de completare aborele se formeaza un sir a[1], a[2],…,a[n] aranjat in piramida , aranjarea consta ca fiecare a[i] sa indeplineasca conditia a[i]<=a[2i]si a[i]<=a[2i+1]. Apoi piramida se foloseste pentru aranjare. Cea mai clara metoda de constructi a piramidei,se uita la aranjarea sirul intr-un arbore, prezentat in fig.2.9. Sirul este reprezentat ca arbore binar a carui virf corespunde cu elimentul sirului a[1]. La nivelul doi se gasesc elementele a[2]si a[3]. La nivelul trei a[4],a[5], a[6] a[7] si asa mai departe. Se observa ca petru un sir cu un numar impar de elemente, arborele va fi echilibrat, dar pentr-un un sir cu un numar par de elimente, n elimente a[n] va fi in partea stinga a foii asemanator cu un arbore ...