Qalaq (verilənlər strukturu)

Tonqal yandırmaq üçün, əvvəlcə odun qalanır. Yeni yandırılmış tonqalda qalaq strukturu hələ də sezilir.

Qovşaq qiymətləri 1 ilə 100 arasında dəyişən ikilik maksimum-qalağa nümunə

Qalaq informatika elmində — xüsusi şərtlərl çərçivəsində təşkil olunmuş ağac şəkilli verilənlər strukturuna deyilir. Gündəlik həyatımızda biz qalaq olaraq bir-birinə dirənərək konus və ya piramida formasında structur yaradan cisimlər (adətən eyni tipli) yığınına deyirik. Dilimizdə "tongal qalamaq" ifadəsi də yandırılacaq cisimlərin əvvəlcə qalaq şəklində yığılması ilə bağlıdır. Qalaq verilənlər strukturunun da forması qalağı xatırlatdığı üçün bu cür adlandırılıb.

Qalağı digər ağaclardan fərqləndirən əsas əlaməti onun həmişə tam və ya tama yaxın olmasıdır, yəni onun çiyinləri kötükdən yarpağa qədər mümkün qədər bərabər hündürlükdə olmalıdır. Ancaq son səviyyə tam olmaya bilər, bu zaman isə son səviyyənin mövcud qovşaqları ağacın mümkün qədər sol yarpaqlarını təşkil etməlidir. Bu isə bir səviyyə tam doldurulmayanadək, növbəti səviyyəyə keçilməməklə təmin edilir. Bu tələblər bir tərəfdən ağacın mümkün olan ən kiçik hündürlüyünü təmin edir, belə ki, N sayda qovşaqdan ibarət ağacın hündürlüyü həmişə $O(log\ N)$ olur, digər tərəfədən isə qalağı xətti (bir ölçülü) massivdə yerləşdirməyə imkan verir.

Qalaq strukturuna olan digər tələb, onun kiçik (min) və ya böyük (max) qalaq olmasından asılı olaraq, qovşağın hər bir törəməsinin özündən böyük ya bərabər və yaxud kiçik ya bərabər olmasıdır. Kiçik qalaq halında bu kötüyün ən kiçik, böyük qalaq halında isə ən böyük element olmasını təmin edir.