Heapsort. Binary Heap asosida tartiblash

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

  1. 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).
  2. Swap. Root’dagi maksimum qiymatli elementni ohirgi element bilan almashtiramiz va uni heap’dan chiqaramiz.
  3. Reheapify. Ohirgi element root bo’lgach, u albatta o’z joyini topishi kerak. Heap tartibini to’g’rilaymiz.
  4. 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