Qalaq Verilenler Strukturu - Wikipedia - Love.az

Qalaq informatika elmində, xüsusi şərtlər çərçivəsində təşkil olunmuş ağacşəkilli verilənlər strukturudur. Gündəlik həyatımızda qalaq dedikdə, adətən bir-birinə dirənərək konus və ya piramida formasında struktur yaradan cisimlər (adətən eyni tipli obyektlər) yığını nəzərdə tutulur. Dilimizdə işlənən "tonqal qalamaq" ifadəsi də yandırılacaq cisimlərin əvvəlcə qalaq şəklində yığılması ilə bağlıdır. Qalaq verilənlər strukturuna da bu adın verilməsi onun formasının bu cür qalaqları xatırlatması ilə əlaqədardır.

Qalağı digər ağac strukturlarından fərqləndirən əsas xüsusiyyət onun həmişə tam və ya tama yaxın ağac olmasıdır. Bu o deməkdir ki, ağacın "çiyinləri" kökdən (kötükdən) yarpaqlara qədər mümkün qədər bərabər hündürlükdə olmalıdır. Lakin son səviyyə tam dolmaya bilər; belə olduqda, mövcud qovşaqlar ağacın mümkün qədər sol tərəfində yerləşməlidir. Bu qayda, bir səviyyə tam doldurulmayınca, növbəti səviyyəyə keçilməməsi ilə təmin edilir.

Bu strukturun üstünlüklərindən biri, onun ağacın mümkün olan ən kiçik hündürlüyünü təmin etməsidir. Belə ki, N sayda qovşaqdan ibarət qalaq ağacın hündürlüyü həmişə ${\displaystyle O(log\ N)}$ sıra mürəkkəbliyinə olur, digər tərəfədən isə qalağı xətti (bir ölçülü) massivdə yerləşdirməyə imkan verir.

Qalaq strukturunun digər mühüm tələbi isə onun kiçik qalaq (min) və ya böyük qalaq (max) olması ilə bağlıdır. Bu halda hər bir qovşağın törəmələri ya ondan böyük və ya bərabər ya da kiçik və ya bərabər olmalıdır. Kiçik qalaq halında, ağacın kök elementi ən kiçik, böyük qalaq halında isə ən böyük element olur.