Heap və Priority Queue

Heap — tam (complete) binary tree-dir və bir invariant saxlayır:

• Min-heap: hər valideyn öz övladlarından kiçik və ya bərabərdir. Ən kiçik element həmişə root-dadır.
• Max-heap: hər valideyn öz övladlarından böyük və ya bərabərdir. Ən böyük element root-dadır.

Diqqət: bu, BST DEYİL. Heap-də qardaşlar arasında heç bir sıra yoxdur — yalnız valideyn–övlad münasibəti nizamlanıb. Ona görə heap-də "filan dəyər varmı?" sualı O(n) tələb edir; heap yalnız bir sualı sürətlə cavablandırır: "ən kiçik (və ya ən böyük) hansıdır?"

Tam ağac olması vacibdir: bütün səviyyələr dolu, yalnız sonuncu səviyyə soldan sağa doldurulub. Məhz bu xüsusiyyət heap-i massivdə saxlamağa imkan verir — heç bir göstərici lazım deyil.

Massivdə indeks riyaziyyatı — heap-in ən zərif hissəsi budur. 0-dan başlayan massivdə:

• parent(i) = (i - 1) / 2 (tam bölmə)
• left(i) = 2 * i + 1
• right(i) = 2 * i + 2

Yəni ağac strukturu tamamilə hesablamadan çıxır. Bu, iki böyük qazanc verir: göstəricilər üçün yaddaş sərf olunmur və bütün data bitişik yaddaşda olduğu üçün cache lokallığı əladır.

İki əsas əməliyyat:

Sift up (heapify up) — yeni element massivin sonuna əlavə olunur, sonra valideyni ilə müqayisə edilib lazım gələrsə yerini dəyişir və bu, invariant bərpa olunana qədər yuxarı doğru davam edir. Ən çoxu ağacın hündürlüyü qədər addım: O(log n).

Sift down (heapify down) — root çıxarılanda sonuncu element root-a qoyulur, sonra iki övladından kiçiyi (min-heap üçün) ilə müqayisə edilib lazım gələrsə aşağı sürüşdürülür. Yenə O(log n).

Bu iki əməliyyat heap-in hər şeyidir: insert sift up, extractMin sift down işlədir.

Build-heap niyə O(n)-dir? Bu, müsahibədə ən çox sürpriz yaradan faktdır.

Sadəlövh mühakimə belədir: n element, hər biri O(log n) sift — deməli O(n log n). Amma düzgün yanaşma elementləri səviyyə üzrə saymaqdır. Aşağıdan yuxarı heapify edəndə:

• Node-ların yarısı leaf-dir və ümumiyyətlə hərəkət etmir (0 addım).
• Dörddə biri ən çoxu 1 addım atır.
• Səkkizdə biri ən çoxu 2 addım atır — və bu, belə davam edir.

Cəm n/2·0 + n/4·1 + n/8·2 + ... sırasıdır və o, 2n-ə yaxınlaşır, yəni O(n). Sadə dillə: node-ların böyük əksəriyyəti aşağıdadır və az iş görür.

Praktik nəticə: hazır massivi heap-ə çevirmək lazımdırsa, n dəfə insert çağırmaq (O(n log n)) yox, aşağıdan yuxarı build-heap (O(n)) etmək lazımdır.

Klassik istifadə halları:

• Top-K — n elementdən ən böyük k-nı tapmaq. Hamısını sıralamaq O(n log n)-dir; k ölçülü min-heap saxlamaq isə O(n log k). k kiçik olanda (məsələn 10) bu, çox böyük fərqdir.
• k sıralı siyahını birləşdirmək — hər siyahının cari elementini heap-də saxlayırsan, ən kiçiyini çıxarıb həmin siyahıdan növbətini əlavə edirsən: O(N log k).
• Planlaşdırma (scheduling) — ən erkən deadline və ya ən yüksək prioritet həmişə root-dadır. Task queue-lar, event loop-lar, Dijkstra alqoritmi.
• Median saxlamaq — iki heap (bir max-heap, bir min-heap) ilə axın üzərində medianı O(log n) yeniləmək.