WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Heapsort. Binary Heap asosida tartiblaş

Sorting

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

  1. **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).
  2. Swap. Root'dagi maksimum qiymatli elementni ohirgi element bilan almaştiramiz va uni heap'dan çiqaramiz.
  3. Reheapify. Ohirgi element root bölgaç, u albatta öz joyini topişi kerak. Heap tartibini töğrilaymiz.
  4. 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