Бул эмне?

Куча (heap) — бул өзгөчө дарактын түзүлүшү, ал куча мүнөздөмөсүн канааттандырат. Бул мүнөздөмө боюнча, ар бир чекит үчүн, тамырдан тышкары, ошол чекиттин ачкыч мааниси анын ата-эне маанисине белгилүү бир катышта болушу керек. Ике негизги түрү бар:

• Макс-куча (Max-heap): Ар бир чекиттин ачкыч мааниси анын балдарынын маанисинен кичине эмес. Эң чоң элемент тамырда жайгашкан.
• Мин-куча (Min-heap): Ар бир чекиттин ачкыч мааниси анын балдарынын маанисинен чоң эмес. Эң кичүү элемент тамырда жайгашкан.

Куча көбүнчө массив түрүндө ишке ашырылат, бул элементтерге эффективдүү жетүү жана операцияларды аткаруу мүмкүнчүлүгүн берет. Массивдеги ата-эне жана балдар ортосундагы байланышты төмөндөгүчө:

• i индекси менен белгиленген элемент үчүн (0дон баштап), анын сол баласы 2i + 1 индексинде жайгашкан.
• Анын оң баласы 2i + 2 индексинде.
• Анын ата-эне floor((i - 1) / 2) индексинде жайгашкан.

Негизги операциялар:

• Insert (Кошуу): Жаңы элемент кошуу. Иш убактысы O(log n), анда n — элементтердин саны.
• Extract-Max / Extract-Min: Максималдуу (max-heap) же минималдуу (min-heap) элементти өчүрүп, кайтаруу. Иш убактысы O(log n).
• Heapify (Кучаны түзүү): Ар кандай массивди кучага айландыруу. Иш убактысы O(n).

Кучалар сорттоо алгоритмдеринде (мисалы, heapsort), артыкчылык кезектери жана эң кыска жолдорду табуу алгоритмдеринде (мисалы, Dijkstra алгоритми) колдонулат.