Bajardi: buronov umid qabul Qildi: Isroilov Sh Samarqand -2022 Heap tree tuzulmasi va ustida amallar bajarish algoritmlari
const array = [null, 100, 70, 80, 20, 30, 20, 50]
Download 238.64 Kb.
|
BURONOV UMID
- Bu sahifa navigatsiya:
- Binary heap ustida amallar
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-nchi elementni ko’rsak: 1.uning parent’i – floor (i-1)/2 indeksda; 2.uning chap child’i – 2 * i indeksda; 3.uning o’ng child’i – 2 *i + 1 indeksda. Binary heap ustida amallar Priority queue’da bo’lgani singari, Binary heap ustida ham ikkita amal bor. Qo’shish (insert yoki enqueue) va eng katta (eng kichik) qiymatini o’chirish (delete yoki dequeue). Shuningdek qo’shilgan va o’chirilgan elementlardan so’ng, heap’ning tartibini to’g’rilash uchun ichki – cho’ktirish (sink) va ko’tarish (swim) amallari ham mavjud. Insert. Heap’ga node (element) qo’shish uchun: 1)Elementni tree’ning eng pastiga qo’shamiz (array’ning ohiriga qo’shamiz). 2)Qo’shilgan elementning parent’iga qaraymiz. Agar parent’i o’zidan katta bo’lsa, ularning o’rnini almashtiramiz. 3)Solishtirish va almashtirishlarni element parent’idan katta bo’lguncha davom ettiramiz. Delete. O’chirish’da biz eng katta (yoki eng kichik) qiymati root’da joylashganini bilganimiz uchun ishimiz osonroq, o’chiriladigan elementni topish O(1) vaqt oladi. O’chirish uchun: 1.root elementni ohirgi element bilan o’rnini almashtiramiz: array[1] ni array[array.length – 1] bilan. Keyin ohirgi elementni o’chiramiz. 2.yangi root’ni uning child’lari bilan solishtiramiz. Agar u child’dan kichik bo’lsa (min heap uchun – child’dan katta bo’lsa), ularning o’rnini almashtiramiz. Ikki child’dan ham kichkina bo’lib qolganda kattaroq qiymatdagi child bilan o’rnini almashtiramiz. 3.shu tariqa solishtirish va almashtirish bilan elementni uning child’larida katta holda qolgunga qadar davom ettiramiz Qo’shish va o’chirish amallarini qanday ishlashini bilib olgach, istalgan tartiblanmagan array’dan binary heap hosil qilishimiz mumkin. Kod: Priority queue kabi, Binary heap’da amallar bittadan ko’p bo’lgani uchun API yozamiz class BinaryHeap { constructor(arr = [], asc = true) { this.arr = arr this.asc = asc } enqueue(item) { // Heap'ga yangi item qo'shamiz this.arr[this.arr.length === 0 ? 1 : this.arr.length] = item // Uning pozitsiyasini to'g'rilaymiz this.swim(this.arr.length - 1) } dequeue() { let max = this.arr[1] // root va ohirgi element o'rnini almashtiramiz. this.arr[1] = this.arr[this.arr.length - 1] this.arr[this.arr.length - 1] = max // Ohirgi elementni o'chiramiz this.arr.pop() // Birinchi elementning pozitsiyasini to'g'rilaymiz. this.sink(1) // O'chirilgan elementning qiymatini qaytaramiz return max } swim(index) { while (index > 1 && ( this.asc && this.arr[Math.floor(index / 2)] > this.arr[index] || !this.asc && this.arr[Math.floor(index / 2)] < this.arr[index] ) ) { // Parent va child o'rnini almashtiramiz this.swap(index, Math.floor(index / 2)) index = Math.floor(index / 2) } } sink(index, len = this.arr.length) { while (Math.floor(index / 2) <= len) { let j = 2 * index if (j < len && ( this.asc && this.arr[j] > this.arr[j + 1] || !this.asc && this.arr[j] < this.arr[j + 1] ) ) { j++ } if (!(this.asc && this.arr[index] > this.arr[j] || !this.asc && this.arr[index] < this.arr[j])) { break } this.swap(index, j) index = j } } isEmpty() { // heap bo'shligini tekshirish return this.arr.length < 2 } swap(a, b) { [this.arr[a], this.arr[b]] = [this.arr[b], this.arr[a]] } show() { return this.arr }} /** * USAGE */ const array = [3, 4, 6, 2, 9, 1] const binaryHeap = new BinaryHeap([], false) array.map(item => binaryHeap.enqueue(item)) binaryHeap.dequeue() console.log(binaryHeap.show()) Download 238.64 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling