Маалыматтардын түзүмүндө стек деген эмне?

Heap — бул атайын дарак түрү, ал маалымат структурасы катары колдонулат. Heapтин негизги өзгөчөлүгү — жарым-жартылай уюшкандык: ар бир түпкү чекит үчүн шарт аткарылат, ал шарт — ата-эне чекиттин мааниси анын балдарынын маанисинен чоң же барабар (макс-heap) же кичи же барабар (минимум-heap).

Негизги өзгөчөлүктөр:

Бинардык дарак: Көбүнчө бинардык дарак түрүндө ишке ашырылат, анда ар бир түпкү чекиттин эң көп эки баласы болот.
Толук бинардык дарак: Бардык деңгээлдерде, акыркы деңгээлден башка, дарак толук толтурулган. Акыркы деңгээлдеги түпкү чекиттер солдон оңго карай толтурулат. Бул heapти массив түрүндө натыйжалуу сактоого мүмкүндүк берет.
Heapтин өзгөчөлүгү:
- Max-heap: Ар бир түпкү чекиттин мааниси анын балдарынын маанисинен чоң же барабар. Эң чоң элемент дайыма түпкү чекитте жайгашкан.
- Min-heap: Ар бир түпкү чекиттин мааниси анын балдарынын маанисинен кичи же барабар. Эң кичи элемент дайыма түпкү чекитте жайгашкан.

Heapтин негизги операциялары:

Элементти кошуу: Жаңы элементти кошуу жана heapтин өзгөчөлүгүн сактоо.
Элементти өчүрүү: Түпкү элементти (эң чоң же эң кичи — heapтин түрүнө жараша) өчүрүү жана heapтин өзгөчөлүгүн сактоо.
Heapти түзүү: Массивден heap түзүү.

Heapтин колдонулушу:

Иреттөө: Heapsort алгоритми.
Приоритеттүү кезектер: Эффективдүү реализациясы, анда элементтер приоритетке ылайык иштетилет.
Издөө алгоритмдери: Мисалы, k-элементти издөө.
Графтык алгоритмдер: Мисалы, Дейкстрас алгоритми.

Heapти массив түрүндө көрсөтүү:

Heap — толук бинардык дарак болгондуктан, ал массивде натыйжалуу сакталат, көрсөткүчтөрдү колдонбостон.

Эгерде түпкү чекит i индексинде болсо, анын сол баласы 2*i + 1 индекси.
Анын оң баласы 2*i + 2 индекси.
Анын ата-эне индекси (i - 1) / 2.

# Min-heapтин массив түрүндөгү мисалы
heap_array = [10, 15, 20, 17, 25, 30]

# Түпкү чекит: heap_array[0] = 10
# Сол баласы: heap_array[2*0 + 1] = heap_array[1] = 15
# Оң баласы: heap_array[2*0 + 2] = heap_array[2] = 20
# Ата-эне индекси 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15