Чӣ гуна аст?

Ҳейп (heap) — бу махсус даражадаги маълумотлар тузилмаси бўлиб, у ҳейп хусусиятини қондиришга мўлжалланган. Бу хусусиятга кўра, ҳар қандай тўп (қовуқ) учун, ўсимликдан ташқари, у тўпнинг калит қиймати муайян муносабатда бўлиши керак. Ҳейпнинг икки асосий тури мавжуд:

• Макс-хейп (Max-heap): Ҳар бир тўпнинг калит қиймати унинг болаларининг қийматларидан кичик бўлмайди. Энг катта элемент ўсимликда жойлашган.
• Мин-хейп (Min-heap): Ҳар бир тўпнинг калит қиймати унинг болаларининг қийматларидан катта бўлмайди. Энг кичик элемент ўсимликда жойлашган.

Ҳейп одатда массив сифатида амалга оширилади, бу эса элементларга самарали кириш ва операцияларни бажариш имконини беради. Массивда ота-она ва болалар ўртасидаги боғланиш қуйидагича:

• i индексидаги элемент учун (0 дан бошланади), унинг сол қўшниси 2i + 1 индексда жойлашган.
• Унинг ўнг қўшниси 2i + 2 индексда.
• Унинг ота-онаси floor((i - 1) / 2) индексда жойлашган.

Асосий операциялар:

• Insert (Қўшиш): Янги элемент қўшиш. Вақт ижро O(log n), бу ерда n — элементлар сони.
• Extract-Max / Extract-Min: Максимум (макс-хейпда) ёки минимум (мин-хейпда) элементни ўчириш ва қайтариш. Вақт ижро O(log n).
• Heapify (Ҳейпни тузиш): Ҳар қандай массивни ҳейпга айлантириш. Вақт ижро O(n).

Ҳейплар сарлаш алгоритмларида (масалан, heapsort), устувор навбатларда ва энг қисқа йўллар қидирув алгоритмларида (масалан, Dijkstra алгоритми) қўлланилади.