Šta je stek (u kontekstu struktura podataka)?

Геј (heap) је специјализовано дрво које се користи као структура података. Главна својство геја је делимично поређење: за сваки врх важи услов да вредност родитељског врха је већа или једнака вредности било ког од његових деце (max-heap) или мања или једнака (min-heap).

Кључне карактеристике:

• Бинарно дрво: Обично се реализује као бинарно дрво, где сваки чвор има највише два потомка.
• Потпуно бинарно дрво: На свим нивоима, осим можда последњег, дрво је потпуно попуњено. Чворови на последњем нивоу се попуњавају са леве на десну. Ово омогућава ефикасно чување геја у виду масива.
• Својство геја:
  • Max-heap: Вредност сваког чвора је већа или једнака вредностима његових потомака. Највећи елемент се увек налази у корену.
  • Min-heap: Вредност сваког чвора је мања или једнака вредностима његових потомака. Најмањи елемент се увек налази у корену.

Основне операције са гејем:

• Додавање елемента: Додавање новог елемента и одржавање својства геја.
• Брисање елемента: Брисање коренског елемента (максималног или минималног у зависности од типа геја) и одржавање својства геја.
• Креирање геја: Конструкција геја из масива елемената.

Примена геја:

• Сортирање: Алгоритам хеапсорт (Heapsort).
• Редови са приоритетом: Ефикасна реализација редова у којима се елементи обрађују по приоритету.
• Алгоритми претраге: На пример, претрага k-ог по величини елемента.
• Алгоритми на графовима: На пример, алгоритам Дејкстри.

Презентација геја у масиву:

Пошто је геј потпуно бинарно дрво, може се ефикасно чувати у масиву без коришћења показивача.

• Ако се чвор налази на индексу 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