O'sish tartibida saralash uchun yig'ma tartiblash algoritmi

HeapSort
Uyumni saralash - Ikkilik uyum ma'lumotlar tuzilishiga asoslangan taqqoslashga asoslangan tartiblash usuli. Bu birinchi navbatda minimal elementni topib, minimal elementni boshida joylashtirgan tanlash tartibiga o'xshaydi. Qolgan elementlar uchun xuddi shu jarayonni takrorlaymiz.
O'sish tartibida saralash uchun yig'ma tartiblash algoritmi:
1. Kirish ma'lumotlaridan maksimal to'plami hosil qilinadi.
2. Ushbu nuqtada, eng katta element uyumning ildizida saqlanadi. Uni to'plamning oxirgi elementi bilan almashtiriladi, so'ngra to'p hajmini 1 ga kamaytiriladi. Nihoyat, daraxt ildizini to'planadi.
3. Uyumning o'lchami 1 dan katta bo'lganda 2-bosqichni takrorlanadi.
To'plamni qanday qurish kerak?
Heapify protsedurasi tugunga faqat uning asosiy tugunlari to'plangan bo'lsa qo'llanilishi mumkin. Shunday qilib, yig'ish pastdan yuqoriga qarab amalga oshirilishi kerak.
Keling, misol yordamida tushunamiz:
Uyma tartiblash qanday ishlaydi?
Uyma tartiblashni aniqroq tushunish uchun keling, saralanmagan massivni olaylik va uni heap sort yordamida saralashga harakat qilaylik.

Shundan so'ng, vazifa saralanmagan massivdan daraxt qurish va uni maksimal to'plamga aylantirishga harakat qilishdir.

Uyumni maksimal yig'maga aylantirish uchun asosiy tugun har doim kichik tugunlardan katta yoki teng bo'lishi kerak

Bu erda, ushbu misolda, ota-tugun 4 10 tugundan kichikroq bo'lgani uchun, ularni maksimal yig'ish uchun almashtiramiz.

Endi, ko'rinib turganidek, ota-ona sifatidagi 4 bola 5 dan kichikroq, shuning uchun ikkalasini ham almashtiring va natijada olingan to'p va massiv quyidagicha bo'lishi kerak:

Keyinchalik, ildiz elementini (10) maksimal to'plamdan o'chirib tashlanadi. Ushbu tugunni o'chirish uchun uni oxirgi tugun bilan almashtirish kerak, ya'ni ildiz elementni olib tashlaganidan so'ng, uni maksimal to'pga aylantirish uchun yana yig'iladi.

Natijadagi to'plam va massiv quyidagicha ko'rinishi kerak:

Yuqoridagi amallarni takrorlagandan so'ng, nihoyat birinchi va oxirgi tugunni almashtiriladi va oxirgi tugunni to'plamdan o'chiriladi va natijada olingan massiv rasmda ko'rsatilganidek tartiblangan ko'rinadi:

Tasvir:
Kiruvchi ma’lumot: {4, 10, 3, 5, 1}

4(0)
/ \
 10(1) 3(2)
/ \
5(3) 1(4)
Qavsdagi raqamlar ma'lumotlarning massiv ko'rinishidagi indekslarni ifodalaydi.
1-indeksga heapify protsedurasini qo'llash:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
0-indeksiga heapify protsedurasini qo'llash:
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
Heapify protsedurasi o'zini yuqoridan pastga qarab yig'ish uchun rekursiv chaqiradi.