Heapsort. Binary Heap asosida tartiblaş
Heapsort - binary heap ma'lumotlar tuzilmasi asosidagi tartiblaş algoritmi. Biz heap har doim ma'lum bir tartibga rioya qilişini bilganimiz uçun, uning bu hususiyatidan tartiblaşda foydalanişimiz - array'ning eng katta qiymatini olib uni array'ning ohiriga qöyib boriş orqali array'ni tartiblaşimiz mumkin.
Heapsort ning işlaş tartibi
- **Heapify. **Tartiblanmagan array'dan max heap yasab olamiz. Binary heap'da hisoblaşni osonlaştiriş uçun array[0] ni böş qoldirgan bölsak, bu safar array[0] iştirok etadi. Sababi hozirgi holatda bizda array tayyor beriladi va qöşimça heap'ni qöşimça özgaruvçiga yiğmasdan array'ning özida yasaymiz (in-place).
- Swap. Root'dagi maksimum qiymatli elementni ohirgi element bilan almaştiramiz va uni heap'dan çiqaramiz.
- Reheapify. Ohirgi element root bölgaç, u albatta öz joyini topişi kerak. Heap tartibini töğrilaymiz.
- Repeat. Ikkinçi va uçinçi qadamlarni heap'da bitta element qolgunça davom ettiramiz.
Vizualizatsiya
Bizdagi max heap
[50, 47, 30, 33, 9, 13, 24, 20, 12, 5]
array'ni tartiblaşni boşlaymiz.

Arrayning birinçi va ohirgi elementlari - 50 va 5 ning örnini almaştiramiz va 50 ni heapdan çiqaramiz. Keyin 5 ni joyiga qöyiş uçun reheapify - qaytadan heap tartibini töğrilaymiz.
5 ikki çild'i - 47 va 30 dan kiçkina. biz uni katta child bilan örnini almaştiramiz.

5 endi özi çild'lari 33 va 9 dan kiçkina. Katta çild'i bilan örnini almaştiramiz.

5 öz çild'i 20 va 12 dan kiçkina. Katta çild'i - 20 bilan örnini almaştiramiz.

Kiçkina element bölgan 5 yana heap'ning pastiga tuşdi, uning çild'i yöq yoki çild'lari bölganda ham ular 5 dan kiçkina bölardi. Reheapify yakunlandi.
Yuqoridagi qadamlarni yana qaytaramiz.

Qolgan qadamlar:

Heapsort'ning işlaş algoritmi Selection sort'ga öxşaydi, ammo heap strukturasi sababli işlaş vaqti selection sort'dan ança tez - O(N log N). Şunga qaramay, Heapsort Mergesort yoki Quicksort kabi tez işlamaydi.
Kod
Note: Funksiya faqat integer sonlarni töğri tartiblaydi. Harflarni yoki string sonlarni töğri tartiblaş uçun «> <» dan boşqa amalni işlatiş kerak. Masalan, ES6 uçun String.prototype.localeCompare() ni işlatib köring.
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/heapsort.js
Mavzu böyiça savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.
Manba: https://medium.com/@anacsanchez/sort-yourself-an-intro-to-heapsort-429ddedd9316