Məlumat strukturları kontekstində yığın nədir?

Yığın (heap), məlumatların struktur kimi istifadə olunduğu ixtisaslaşmış bir ağacdır. Yığın (heap) əsas xüsusiyyəti qismən sıralamadır: hər bir düyün üçün, valideyn düyününün dəyəri onun hər hansı bir uşağının dəyərindən böyük və ya bərabər olmalıdır (max-heap) və ya kiçik və ya bərabər olmalıdır (min-heap).

Əsas xüsusiyyətlər:

İkili ağac: Ən çox ikili ağac kimi həyata keçirilir, hər bir düyünün ən çox iki övladı olur.
Tam ikili ağac: Bütün səviyyələrdə, bəlkə də sonuncu, ağac tam doldurulmuşdur. Son səviyyədəki düyünlər soldan sağa doldurulur. Bu, heap-in səmərəli şəkildə massiv kimi saxlanmasına imkan verir.
Heap-in xüsusiyyəti:
- Max-heap: Hər bir düyünün dəyəri onun uşaqlarının dəyərlərindən böyük və ya bərabərdir. Ən böyük element həmişə kökdə yerləşir.
- Min-heap: Hər bir düyünün dəyəri onun uşaqlarının dəyərlərindən kiçik və ya bərabərdir. Ən kiçik element həmişə kökdə yerləşir.

Əsas əməliyyatlar:

Element əlavə etmək: Yeni element əlavə etmək və heap-in xüsusiyyətini qorumaq.
Element silmək: Kök elementini (maksimum və ya minimum, heap-in növündən asılı olaraq) silmək və heap-in xüsusiyyətini qorumaq.
Heap qurmaq: Elementlər massivindən heap qurmaq.

Heap-in tətbiqləri:

Sıralama: Heap sıralama algoritmi (Heapsort).
Prioritetli növbələr: Elementlərin prioritetə görə işlənməsi üçün səmərəli tətbiq.
Axtarış algoritmləri: Məsələn, k-ci ən böyük elementi tapmaq.
Qraf algoritmləri: Məsələn, Dijkstra algoritmi.

Heap-in massivdə nümayişi:

Heap tam ikili ağac olduğundan, onu göstəricilər istifadə etmədən səmərəli şəkildə saxlamaq mümkündür.

Əgər düyün i indeksindədirsə, onun sol övladı 2*i + 1 indeksindədir.
Onun sağ övladı 2*i + 2 indeksindədir.
Onun valideyni (i - 1) / 2 indeksindədir.

# Min-heap-in massiv kimi nümayişi nümunəsi
heap_array = [10, 15, 20, 17, 25, 30]

# Kök: heap_array[0] = 10
# Kökün sol övladı: heap_array[2*0 + 1] = heap_array[1] = 15
# Kökün sağ övladı: heap_array[2*0 + 2] = heap_array[2] = 20
# 3-cü indeksdəki elementin valideyni: heap_array[(3-1)//2] = heap_array[1] = 15