Yığın nədir?

Yığım (heap), xüsusi bir ağac quruluşudur və yığım xüsusiyyətini təmin edir. Bu xüsusiyyət deyir ki, hər hansı bir ulduz üçün, kök xaricində, bu ulduzun açar dəyəri onun valideyninin açar dəyəri ilə müəyyən bir münasibətdə olmalıdır. İki əsas növ yığın mövcuddur:

• Max-yığın (Max-heap): Hər bir ulduzun açar dəyəri onun uşaqlarının dəyərindən kiçik deyil. Ən böyük element kökdə yerləşir.
• Min-yığın (Min-heap): Hər bir ulduzun açar dəyəri onun uşaqlarının dəyərindən böyük deyil. Ən kiçik element kökdə yerləşir.

Yığın adətən massiv kimi həyata keçirilir, bu da elementlərə effektiv giriş və əməliyyatların yerinə yetirilməsini təmin edir. Massivdə valideyn və uşaqlar arasındakı əlaqə aşağıdakı kimidir:

• i indeksli element üçün (sıfırdan başlayaraq), onun sol uşağı 2i + 1 indeksində yerləşir.
• Onun sağ uşağı 2i + 2 indeksində yerləşir.
• Onun valideyni floor((i - 1) / 2) indeksində yerləşir.

Yığın üzərində əsas əməliyyatlar:

• Əlavə et (Insert): Yeni element əlavə etmək. İş vaxtı O(log n), burada n elementlərin sayıdır.
• Extract-Max / Extract-Min: Maksimal (max-yığın) və ya minimal (min-yığın) elementi silib geri qaytarmaq. İş vaxtı O(log n).
• Heapify (Yığın quruluşu): Hər hansı bir massivdən yığın yaratmaq. İş vaxtı O(n).

Yığınlar sıralama algoritmlərində (məsələn, yığın sıralaması), prioritetli növbələrdə və ən qısa yolların axtarışında (məsələn, Dijkstra algoritmi) istifadə olunur.