Sobes.tech
Intervyu yordami
Resurslar
Intervyuga tayyorgarlik
Resurslar
Ish qidirish
Resurslar
Huquqiy
Savollarga qaytish
Middle

Ma'lumotlar tuzilmasi kontekstida stek nima?

sobes.tech AI

AIdan javob

Yig'indi (heap) ma'lumotlar tuzilmasi sifatida ishlatiladigan maxsus daraxtdir. Yig'indining asosiy xususiyati qisman tartiblashdir: har qanday tugun uchun, ota tugunning qiymati uning har qanday bolalarining qiymatidan katta yoki teng bo'lishi shart (max-heap) yoki kichik yoki teng bo'lishi shart (min-heap).

Asosiy xususiyatlar:

  • Ikki tarmoqli daraxt: Ko'pincha ikki tarmoqli daraxt sifatida amalga oshiriladi, har bir tugun kamida ikki bolaga ega.
  • To'liq ikki tarmoqli daraxt: Barcha darajalarda, ehtimol, oxirgi darajada, daraxt to'liq to'ldirilgan. Oxirgi darajadagi tugunlar chapdan o'ngga to'ldiriladi. Bu yig'indini samarali tarzda massiv sifatida saqlash imkonini beradi.
  • Yig'indi xususiyati:
    • Max-heap: Har bir tugunning qiymati uning bolalarining qiymatidan katta yoki teng bo'ladi. Eng katta element doimo ildizda joylashgan.
    • Min-heap: Har bir tugunning qiymati uning bolalarining qiymatidan kichik yoki teng bo'ladi. Eng kichik element doimo ildizda joylashgan.

Yig'indi bilan asosiy operatsiyalar:

  • Element qo'shish: Yangi element qo'shish va yig'indining xususiyatini saqlash.
  • Elementni o'chirish: Ildiz elementini (maksimal yoki minimal, yig'indining turiga qarab) o'chirish va yig'indining xususiyatini saqlash.
  • Yig'indini qurish: Elementlar massividan yig'indini qurish.

Yig'indining qo'llanilishi:

  • Tartiblash: Yig'indili tartiblash algoritmi (Heapsort).
  • Prioritetli navbatlar: Elementlar prioritet bo'yicha ishlov beriladigan samarali navbatlar.
  • Qidiruv algoritmlari: Masalan, k-chi eng katta elementni qidirish.
  • Graf algoritmlari: Masalan, Dijkstra algoritmi.

Yig'indini massivda ifodalash:

Yig'indi to'liq ikki tarmoqli daraxt bo'lgani uchun, uni ko'rsatkichlarsiz samarali saqlash mumkin.

  • Agar tugun i indeksda bo'lsa, uning chap bolasi 2*i + 1 indeksda joylashgan.
  • Uning o'ng bolasi 2*i + 2 indeksda joylashgan.
  • Uning ota tuguni (i - 1) / 2 indeksda joylashgan.
# Min-heap ni massiv shaklida ifodalash misoli
heap_array = [10, 15, 20, 17, 25, 30]

# Asos: heap_array[0] = 10
# Asosning chap bolasi: heap_array[2*0 + 1] = heap_array[1] = 15
# Asosning o'ng bolasi: heap_array[2*0 + 2] = heap_array[2] = 20
# 3-indeksdagi elementning ota tuguni: heap_array[(3-1)//2] = heap_array[1] = 15
OldingiKeyingi