Heap sort haqida
Mundarija Kirish. Uyumni saralash algoritmi ................................................................................................................ 2 I bob. Heap sort ........................................................................................................................................... 2 1.1.Heap sort algoritmi haqida .................................................................................................................... 3 1.2.heap sort algoritmini c++ da kodi ........................................................................................................ 13 Uymli saralash murakkabligi ...................................................................................................................... 14 Xulosa. ....................................................................................................................................................... 26 Manbalar ................................................................................................................................................... 27 1
Kirish. Uyumni saralash algoritmi Heap Sort - bu kompyuter dasturlashda mashhur va samarali tartiblash algoritmi . Uyumli tartiblash algoritmini yozishni o'rganish uchun ikki turdagi ma'lumotlar tuzilmalarini - massivlarni va daraxtlarni bilish kerak. I bob. Heap sort Biz tartiblamoqchi bo'lgan dastlabki raqamlar to'plami massivda saqlanadi, masalan [10, 3, 76, 34, 23, 32], tartiblangandan so'ng biz tartiblangan massivni olamiz [3,10,23,32,34,76]. Uyumni saralash massiv elementlarini to'liq ikkilik daraxtning maxsus turi sifatida tasvirlash orqali ishlaydi. Eslatma: Majburiy shart sifatida siz to'liq ikkilik daraxt va yig'ma ma'lumotlar tuzilishi haqida bilishingiz kerak . Massiv indekslari va daraxt elementlari o'rtasidagi bog'liqlik To'liq ikkilik daraxt qiziqarli xususiyatga ega bo'lib, biz har qanday tugunning bolalari va ota-onalarini topish uchun foydalanishimiz mumkin. Agar massivdagi biron bir elementning indeksi bo'lsai, indeksdagi 2i+1element chap bolaga, 2i+2indeksdagi element esa o'ng yordamchiga aylanadi. Shuningdek, indeksdagi har qanday elementning ota-onasi i ning pastki chegarasi bilan berilgan (i-1)/2. Massiv va to'p indekslari o'rtasidagi bog'liqlik Keling, sinab ko'raylik, Chap bola 1 (indeks 0) = (2*0+1) indeksdagi element = 1 indeksdagi element = 12 1 bolaning o'ng farzandi 2
= (2*0+2) indeksdagi element = 2 indeksdagi element = 9 Xuddi shunday, 12 yoshli chap bola (indeks 1) = (2*1+1) indeksdagi element = 3 indeksdagi element = 5 12 yoshli o'ng bola = (2*1+2) indeksdagi element = 4 indeksdagi element = 6 Keling, har qanday tugunning ota-onasini topish uchun qoidalar mavjudligini tasdiqlaylik 9 bolaning ota-onasi (2-pozitsiya) = (2-1)/2 = ½ = 0,5 ~ 0 indeks = 1 12 yoshli ota-ona (1-pozitsiya) = (1-1)/2 = 0 indeks = 1 Massiv indekslarini daraxt pozitsiyalariga solishtirishni tushunish, yig'ma ma'lumotlar tuzilmasi qanday ishlashini va undan yig'ish saralashni amalga oshirishda qanday ishlatilishini tushunish uchun juda muhimdir. Uyma ma'lumotlar strukturasi nima? 1.1.Heap sort algoritmi haqida Heap - bu daraxtga asoslangan maxsus ma'lumotlar tuzilmasi. Ikkilik daraxt to'plangan ma'lumotlar strukturasiga amal qiladi, deyiladi if bu to'liq ikkilik daraxtdir Daraxtdagi barcha tugunlar o'z farzandlaridan katta bo'lgan xususiyatga amal qiladi, ya'ni eng katta element ildizda va uning ikkala bolalari va ildizdan kichikroq va hokazo. Bunday to'p max-heap deb ataladi. Buning o'rniga, barcha tugunlar o'z farzandlaridan kichikroq bo'lsa, u min-to'p deb ataladi 3
Quyidagi misol diagrammasi Max-Heap va Min-Heapni ko'rsatadi. 4
Maks to'p va min yig'im Daraxtni qanday qilib "to'plash" mumki n. To'liq ikkilik daraxtdan boshlab, biz to'plamning barcha barg bo'lmagan elementlarida heapify deb nomlangan funktsiyani ishga tushirish orqali uni Max-Heapga aylantirishimiz mumkin. Heapify rekursiyadan foydalanganligi sababli, uni tushunish qiyin bo'lishi mumkin. Shunday qilib, keling, birinchi navbatda, uchta element bilan daraxtni qanday yig'ish kerakligini o'ylab ko'raylik. heapify(array) Root = array[0] Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2]) if(Root != Largest) Swap(Root, Largest) 5