Kirish: I. Ma’lumotlar tuzilmasini saralash usullari

1.7. Pufakcha (qalqib chiqish) usuli.

Maks-heapify (A, 2) ta’sir qiladi, bu erda A.heap- size = 10. (a) Boshlang'ich konfiguratsiya, A [2] tugmachasida i = 2, har ikkala boladan kattaroq boMgani uchun maksirnal birikma xususiyatini buzadi. Maks-birikma xususiyati 4-tugma uchun tiklanadi. Max-heapify (A, 4) o^z-o^zidan yineluvchi chaqiruvi i = 4 ga ega. A [4] ni [9] bilan o‘zgartirib bo‘lgach, (s) da ko’rsatilgandek, tugun 4 ga o‘rnatildi va Max-Heapify (A, 9) takrorlangan chaqiruvi ma’lumotlar tuzilmasiga boshqa hech qanday o‘zgartirish bermaydi.

Aylantirish jarayonida triad elementlari ikki marotaba taqqoslanadi (10-chizma), shu bilan birga eng katta element yuqoriga, eng kichik element esa pastga o‘tadi.

10-chizma. Triad elementlarini taqqoslash: 1-birinchi taqqoslash; 2- ikkinchi taqqoslash;15

n = A.length bo‘lgan A [l..n ] kirish massivida o‘smovchi piramidani qurish uchun pirarnida usulida saralash algoritmi BUILD-MAX-HEAP protsedurasini chaqirishdan boshlanadi. Massivning eng katta element! A[ 1] bo'lganligi sababli, uni Л[п] elementi o‘rni bilan almashtirib, saralangan massivning aniq va oxirgi pozitsiyaga qo‘yish mumkin.

Piramidali saralash (A)

1 Build-Max-Heap (A)

2 for i A.length downto 2

3 exchange A[1 J with A[i]

4 A.heap-size = A.heap-size-1

5 Max-Heapify (A,l)

1-qatorda boshlang‘ich o‘smovchi pirarnida qurilgandan so‘ng HEAPSORT protsedurasini ishlashi keltirilgan. Chizmada 2-5 qatorlarda birinchi va keyingi har bir for silk interatsiyasidan o‘smovchi pirarnida ko'rsatilgan. BUILD-MAX-HEAP protsedurasini chaqirish 0(n) vaqt talab etishi hamda MAX-HEAPIFY protsedurasining har bir n-1 chaqi- ruv vaqti 0(lgn) ga teng ekanligidan, HEAPSORT protsedurasining ish vaqti 0(nlgn) ga teng bo‘ladi.