Nima bu yigit?

Yig'indi (heap) — bu maxsus daraxt tuzilishi bo'lib, u yigin xususiyatini qanoatlantiradi. Bu xususiyat shuni anglatadiki, har qanday tugun uchun, ildizdan tashqari, bu tugunning kalit qiymati uning ota-ning qiymati bilan ma'lum bir nisbatda bo'lishi kerak. Yig'inning ikki asosiy turi mavjud:

• Max-yig'indi (Max-heap): Har bir tugunning kalit qiymati uning bolalarining qiymatidan kam bo'lmaydi. Eng katta element ildizda joylashgan.
• Min-yig'indi (Min-heap): Har bir tugunning kalit qiymati uning bolalarining qiymatidan katta bo'lmaydi. Eng kichik element ildizda joylashgan.

Yig'in odatda massiv sifatida amalga oshiriladi, bu esa elementlarga samarali kirish va operatsiyalarni bajarishga imkon beradi. Massivda ota- va bolalar o'rtasidagi bog'lanish quyidagicha:

• i indeksli element uchun (0 dan boshlanadi), uning chap bolasi 2i + 1 indeksda joylashgan.
• Uning o'ng bolasi 2i + 2 indeksda.
• Uning ota-esi floor((i - 1) / 2) indeksda joylashgan.

Yig'in ustida asosiy operatsiyalar:

• Insert (Qo'shish): Yangi element qo'shish. Ish vaqti O(log n), bu yerda n elementlar soni.
• Extract-Max / Extract-Min: Eng katta (max-yig'inda) yoki eng kichik (min-yig'inda) elementni o'chirish va qaytarish. Ish vaqti O(log n).
• Heapify (Yig'indi qurish): Har qanday massivni yig'inga aylantirish. Ish vaqti O(n).

Yig'inlar saralash algoritmlarida (masalan, yigin bilan saralash), ustuvorlik navbatlarida va eng qisqa yo'l algoritmlarida (masalan, Dijkstra algoritmi) ishlatiladi.