Proqramlaşdırma kontekstində yığın nədir və hansı növ yığınlar mövcuddur?

Yığın (Heap), proqramın icrası zamanı dinamik yaddaş ayırması üçün istifadə olunan yaddaş sahəsidir.

Əsas xüsusiyyətlər:

• Yaddaş açıq şəkildə proqramçı (və ya çöp toplayıcı) tərəfindən ayrılır və sərbəst buraxılır.
• Yaddaş bloklarının ayırması və sərbəst buraxılması üçün sərt ardıcıllıq yoxdur.
• Yaddaş idarəetməsi yığındakı kimi daha mürəkkəbdir, parçalanma və yaddaş sızmalarına səbəb ola bilər.

Məlumat strukturları kontekstində yığın növləri:

• İkili yığın (Binary Heap): Yığın xüsusiyyətini təmin edən ağac. Hər hansı bir düyün (kök istisna olmaqla), onun dəyəri valideynin dəyərindən kiçik və ya böyükdür.
  • Min Yığın: Valideynin dəyəri həmişə uşaqların dəyərindən kiçik və ya bərabərdir. Ən kiçik element kökdə yerləşir.
  • Max Yığın: Valideynin dəyəri həmişə uşaqların dəyərindən böyük və ya bərabərdir. Ən böyük element kökdə yerləşir.
• Binomiyal yığın (Binomial Heap): Müəyyən xüsusiyyətləri təmin edən binomiyal ağacların kolleksiyası. Effektiv birləşmə əməliyyatlarını dəstəkləyir.
• Fibonacci yığını (Fibonacci Heap): Dijkstra kimi alqoritmlərdə istifadə olunan məlumat strukturu. Bəzi əməliyyatlar üçün daha effektiv amortizasiya vaxtları təmin edir.
• Pairing Heap: Sadə tətbiq olunan və yaxşı amortizasiya vaxtlarına malik məlumat strukturu.
• Sol Yığın (Leftist Heap): Effektiv birləşməni asanlaşdıran məlumat strukturu. Əhəmiyyətli xüsusiyyət "rütbə" və ya "sıfır uzunluq yolu" dür və sürətli birləşmə üçün istifadə olunur.

Bu yığın növləri müxtəlif alqoritmlərdə istifadə olunur, məsələn, sıralama (Heap Sort), prioritet növbələrin tətbiqi, ən qısa yol tapma alqoritmləri və s. Xüsusi yığın növünün seçimi tələb olunan əməliyyatlar və onların vaxt effektivliyinə bağlıdır.