WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Binary Heap ma'lumotlar töplami

binary heap

Binary heap - har bir tuguni (node) maxsus tartiblangan va complete binary tree.

Complete binary tree nima ekanligi haqida bu yerda tuşuntirib ötilgani uçun, maxsus tartiblangan ma'nosiga töxtalamiz.

Binary heap bölişi uçun tree'da ma'lumotlar şajara böyiça ösiş tartibida (max heap) yoki kamayiş tartibida (min heap) joylaşgan bölişi kerak.

  1. Max-Heap bölişi uçun har bir node'ning qiymati uning parent node'ining qiymatidan kiçik yoki teng bölişi kerak. Eng katta qiymat root'da böladi. Qoida tree'dagi barça node'lar uçun amal qiladi.
  2. Min-Heap bölişi uçun har bir node'ning qiymati uning parent node'ining qiymatidan katta yoki teng bölişi kerak. Eng kiçkina qiymat root'da böladi. Qoida tree'dagi barça node'lar uçun amal qiladi.

Max Heap va Min Heap. Image credit: https://link.medium.com/pn5E85sTeab Max Heap va Min Heap. Image credit: https://link.medium.com/pn5E85sTeab

Binary heap nima uçun kerak?

Qisqa javob - heap'dagi eng katta (yoki eng kiçik) elementni topiş uçun kerak. Bunda binary heap tuzilişi tree bölgani uçun eng pastki elementdan eng yuqori elementga çiqiş uçun O (log N) uriniş lozim. Masalan yuqoridagi rasmda har bir tree'da 7 ta node bölsa, pastdan yuqoriga çiqiş - log27 = 2.8 ~ 2 ta urinişda böladi.

Priority queue maqolasida biz röyhatdan eng katta va eng kiçik elementni topişni körgan edik. Uning kamçiligi - tartiblanmagan array uçun eng katta (yoki eng kiçik) elementni topişda time complexity O(N) bölib ketayotgan edi. Tartiblangan array uçun esa, eng katta (eng kiçik) elementni topiş O(1) böladi, lekin bunda array element qöşganimizda har safar array'ni tartiblaşga majbur bölinardi - O(N log N).

Demak, Binary heap Priority queue'dan köra samaraliroq işlaydi. Qöşiş va öçiriş - binary tree'dagi kabi O (log N).

Binary heap'ning kamçiligi - u faqat eng katta (eng kiçkina) elementlarni tezda topiş imkonini beradi. Boşqa qiymatdagi elementlarni topiş uçun heapni "titkilab" çiqiş kerak. Sababi binary heap - tartiblanmagan. Tabiiyki tartiblanmagan röyhatdan qidiriş O(N) vaqtni oladi. Masalan yuqoridagi rasm'dan 30 sonini topiş uçun heap'ning hamma elementlari tekşirib çiqiş kerak böladi.

Kodda ifodalaş

Binary heap uçun double pointer'li linked list işlatiş şartmas. Şunçaki array bilan ham ifodalasa böladi.

Amallar osonroq bölişi uçun array[0] ni böş qoldiramiz, keyin heap qiymatlarini kiritamiz. Bizda Max heap'ni kodda ifodalaş

const array = [null, 100, 70, 80, 20, 30, 20, 50]

Min heap:

const array = [null, 10, 14, 17, 20, 30, 21, 44]

Agar biz array'dan i-nçi elementni körsak:

  • uning parent'i - floor (i-1)/2 indeksda;
  • uning çap çild'i - 2 * i indeksda;
  • uning öng çild'i - 2 *i + 1 indeksda.

Binary heap ustida amallar

Priority queue'da bölgani singari, Binary heap ustida ham ikkita amal bor. Qöşiş (insert yoki enqueue) va eng katta (eng kiçik) qiymatini öçiriş (delete yoki dequeue). Şuningdek qöşilgan va öçirilgan elementlardan söng, heap'ning tartibini töğrilaş uçun içki - çöktiriş (sink) va kötariş (swim) amallari ham mavjud.

Insert. Heap'ga node (element) qöşiş uçun:

  1. Elementni tree'ning eng pastiga qöşamiz (array'ning ohiriga qöşamiz).
  2. Qöşilgan elementning parent'iga qaraymiz. Agar parent'i özidan katta bölsa, ularning örnini almaştiramiz.
  3. Soliştiriş va almaştirişlarni element parent'idan katta bölgunça davom ettiramiz.

Max heap uçun insert amali. Image credit: https://dsucbasic.blogspot.com/2016/?m=0 Max heap uçun insert amali. Image credit: https://dsucbasic.blogspot.com/2016/?m=0

Delete. Öçiriş'da biz eng katta (yoki eng kiçik) qiymati root'da joylaşganini bilganimiz uçun işimiz osonroq, öçiriladigan elementni topiş O(1) vaqt oladi.

Öçiriş uçun:

  1. root elementni ohirgi element bilan örnini almaştiramiz: array[1] ni array[array.length - 1] bilan. Keyin ohirgi elementni öçiramiz.
  2. yangi root'ni uning çild'lari bilan soliştiramiz. Agar u çild'dan kiçik bölsa (min heap uçun - çild'dan katta bölsa), ularning örnini almaştiramiz. Ikki çild'dan ham kiçkina bölib qolganda kattaroq qiymatdagi child bilan örnini almaştiramiz.
  3. şu tariqa soliştiriş va almaştiriş bilan elementni uning çild'larida katta holda qolgunga qadar davom ettiramiz.

Max heap uçun delete amali. Image credit: https://dsucbasic.blogspot.com/2016/?m=0 **Max heap uçun delete amali. Image credit: https://dsucbasic.blogspot.com/2016/?m=0

Qöşiş va öçiriş amallarini qanday işlaşini bilib olgaç, istalgan tartiblanmagan array'dan binary heap hosil qilişimiz mumkin.

Kod

Priority queue kabi, Binary heap'da amallar bittadan köp bölgani uçun API yozamiz.

Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/priority-queues/binary-heap.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.