Heapsort – binary heap ma’lumotlar tuzilmasi asosidagi tartiblash algoritmi. Biz heap har doim ma’lum bir tartibga rioya qilishini bilganimiz uchun, uning bu hususiyatidan tartiblashda foydalanishimiz – array’ning eng katta qiymatini olib uni array’ning ohiriga qo’yib borish orqali array’ni tartiblashimiz mumkin.
Heapsort ning ishlash tartibi
- Heapify. Tartiblanmagan array’dan max heap yasab olamiz. Binary heap’da hisoblashni osonlashtirish uchun array[0] ni bo’sh qoldirgan bo’lsak, bu safar array[0] ishtirok etadi. Sababi hozirgi holatda bizda array tayyor beriladi va qo’shimcha heap’ni qo’shimcha o’zgaruvchiga yig’masdan array’ning o’zida yasaymiz (in-place).
- Swap. Root’dagi maksimum qiymatli elementni ohirgi element bilan almashtiramiz va uni heap’dan chiqaramiz.
- Reheapify. Ohirgi element root bo’lgach, u albatta o’z joyini topishi kerak. Heap tartibini to’g’rilaymiz.
- Repeat. Ikkinchi va uchinchi qadamlarni heap’da bitta element qolguncha davom ettiramiz.
Vizualizatsiya
Bizdagi max heap
[50, 47, 30, 33, 9, 13, 24, 20, 12, 5]
array’ni tartiblashni boshlaymiz.
Arrayning birinchi va ohirgi elementlari – 50 va 5 ning o’rnini almashtiramiz va 50 ni heapdan chiqaramiz. Keyin 5 ni joyiga qo’yish uchun reheapify – qaytadan heap tartibini to’g’rilaymiz.
5 ikki child’i – 47 va 30 dan kichkina. biz uni katta child bilan o’rnini almashtiramiz.
5 endi o’zi child’lari 33 va 9 dan kichkina. Katta child’i bilan o’rnini almashtiramiz.
5 o’z child’i 20 va 12 dan kichkina. Katta child’i – 20 bilan o’rnini almashtiramiz.
Kichkina element bo’lgan 5 yana heap’ning pastiga tushdi, uning child’i yo’q yoki child’lari bo’lganda ham ular 5 dan kichkina bo’lardi. Reheapify yakunlandi.
Yuqoridagi qadamlarni yana qaytaramiz.
Qolgan qadamlar:
Heapsort’ning ishlash algoritmi Selection sort‘ga o’xshaydi, ammo heap strukturasi sababli ishlash vaqti selection sort’dan ancha tez – O(N log N). Shunga qaramay, Heapsort Mergesort yoki Quicksort kabi tez ishlamaydi.
Kod
Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni to’g’ri tartiblash uchun «> <» dan boshqa amalni ishlatish kerak. Masalan, ES6 uchun String.prototype.localeCompare() ni ishlatib ko’ring.
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/heapsort.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.
* * *
Manba: https://medium.com/@anacsanchez/sort-yourself-an-intro-to-heapsort-429ddedd9316