Heap va Priority Queue

Kasalxona qabul xonasini tasavvur qiling: navbat bor, lekin bu oddiy navbat emas — og'irroq bemor kelsa, u oldingi navbatdan o'tadi. Har kim kirganda navbat qayta tartiblangandek ko'rinadi, aslida esa tizim doim eng muhimni oldinda saqlaydi. Aynan shu "eng muhimni tez topish" — heap va priority queue'ning asosi.

Priority Queue nima?

Priority Queue — har elementning ustuvorligi bo'lgan navbat. ENQUEUE elementni qo'shadi, DEQUEUE esa navbatda eng ustunini (eng kichik yoki eng katta ustuvorlikni) olib chiqadi.

Ikki turi: - Min priority queue: DEQUEUE eng kichik elementni chiqaradi. - Max priority queue: DEQUEUE eng kattasini chiqaradi.

Oddiy navbatda DEQUEUE qo'shilgan birinchi elementni qaytaradi (FIFO). Priority queue'da tartib emas, ustuvorlik muhim.

Heap nima?

Heap — priority queue'ni samarali amalga oshiruvchi ma'lumotlar tuzilmasi. U to'liq binar daraxt (complete binary tree) bo'lib, qo'shimcha tartib xususiyatini saqlaydi.

Min-heap: har tugunning qiymati uning bolalaridan kichik yoki teng. Natijada ildiz — eng kichik element.

        [1]
       /   \
     [3]   [2]
    / \   /
  [9] [7][5]

1 ≤ 3, 1 ≤ 2, 3 ≤ 9, 3 ≤ 7, 2 ≤ 5 — heap xususiyati bajarilgan.

Max-heap: har tugunning qiymati uning bolalaridan katta yoki teng. Ildiz — eng katta element.

        [9]
       /   \
     [7]   [8]
    / \   /
  [3] [2][5]

Heap xususiyati har ota-bola juftligi uchun saqlanishi kerak. Aka-uka tugunlar o'rtasida hech qanday tartib kafolatlanmaydi.

Heap massivda saqlanadi

Heap doim to'liq binar daraxt (complete binary tree) sifatida quriladi — barcha qavatlari to'la, oxirgi qavat elementlari chapga joylashgan. Bu xususiyat heapni massivda bo'sh joy qoldirmasdan saqlashga imkon beradi.

        [1]           Massiv: [1, 3, 2, 9, 7, 5]
       /   \          Index:   0  1  2  3  4  5
     [3]   [2]
    / \   /
  [9] [7][5]

i-indeks uchun:
  Chap bola:  2*i + 1
  O'ng bola:  2*i + 2
  Ota-ona:    (i - 1) / 2   (butun bo'linish)

Tekshirish: i=1 (qiymat 3): chap 2*1+1=3 (qiymat 9) ✓, o'ng 2*1+2=4 (qiymat 7) ✓, ota (1-1)/2=0 (qiymat 1) ✓.

Massiv asosidagi ifodalash pointer'lar kerak emas, cache-friendly va xotira samarali.

Asosiy amallar

Qo'shish (PUSH / ENQUEUE)

Yangi element massivning oxiriga qo'shiladi (to'liq binar daraxt xususiyatini saqlash uchun). Keyin heap xususiyatini tiklash uchun u yuqoriga "suzib chiqadi" — sift up (yoki bubble up).

FUNCTION PUSH(heap, value)
    heap oxiriga value qo'sh
    i = oxirgi index

    WHILE i > 0
        parent = (i - 1) / 2

        IF heap[parent] ≤ heap[i]   // min-heap uchun
            BREAK                   // heap xususiyati bajarilgan

        heap[parent] va heap[i] ni almashtir
        i = parent

Min-heap ga 4 qo'shish:

Boshlang'ich:   [1, 3, 2, 9, 7, 5]

1. 4 ni oxiriga qo'sh:
   [1, 3, 2, 9, 7, 5, 4]
   i=6, parent=(6-1)/2=2 (qiymat 2)

2. heap[2]=2 ≤ heap[6]=4 → BREAK. Heap xususiyati saqlangan.

Natija: [1, 3, 2, 9, 7, 5, 4]

Boshqa misol — 0 qo'shish:

Boshlang'ich:   [1, 3, 2, 9, 7, 5]

1. 0 ni oxiriga:
   [1, 3, 2, 9, 7, 5, 0]
   i=6, parent=2 (qiymat 2)

2. heap[2]=2 > heap[6]=0 → almashtir
   [1, 3, 0, 9, 7, 5, 2]
   i=2, parent=0 (qiymat 1)

3. heap[0]=1 > heap[2]=0 → almashtir
   [0, 3, 1, 9, 7, 5, 2]
   i=0 → BREAK (ildizga yetdik)

Natija: [0, 3, 1, 9, 7, 5, 2]

O'chirish — minimum (POP / DEQUEUE)

Ildiz — eng kichik element. Uni olib chiqiladi, lekin qanday? Ildizni olib tashlasak, ikkita kenja daraxt yetim qoladi.

Yechim: 1. Ildizni oxirgi element bilan almashtir. 2. Oxirgi elementni o'chir. 3. Yangi ildiz to'g'ri joyiga "cho'kib tushsin" — sift down.

FUNCTION POP(heap)
    IF heap bo'sh
        RETURN NULL

    min_value = heap[0]
    heap[0] = heap'ning oxirgi elementi
    heap'dan oxirgi elementni o'chir

    SIFT_DOWN(heap, 0)
    RETURN min_value

FUNCTION SIFT_DOWN(heap, i)
    n = heap hajmi

    WHILE TRUE
        smallest = i
        left  = 2*i + 1
        right = 2*i + 2

        IF left < n AND heap[left] < heap[smallest]
            smallest = left

        IF right < n AND heap[right] < heap[smallest]
            smallest = right

        IF smallest = i
            BREAK   // to'g'ri joyida

        heap[i] va heap[smallest] ni almashtir
        i = smallest

Dry run — [1, 3, 2, 9, 7, 5] dan minimum olamiz:

1. ildiz (1) ni saqlaymiz, oxirgi (5) ni ildizga o'tkazamiz:
   [5, 3, 2, 9, 7]   (6→5 ta element)

2. SIFT_DOWN(0):
   i=0 (5): left=1 (3), right=2 (2)
   smallest=2 (qiymat 2, chunki 2 < 3 < 5)
   5 va 2 ni almashtir:
   [2, 3, 5, 9, 7]
   i=2

3. i=2 (5): left=5, right=6 → ikkisi ham mavjud emas (n=5)
   smallest=2, BREAK

Natija: [2, 3, 5, 9, 7]   qaytarilgan: 1

Peek — minimumni o'qish

FUNCTION PEEK(heap)
    RETURN heap[0]

O(1) — eng muhim amalni (min/max'ni ko'rish) tezkor bajarish.

Vaqt murakkabligi

Amal	Murakkablik	Sabab
PUSH	`O(log n)`	Sift up — balandlik bo'yicha
POP	`O(log n)`	Sift down — balandlik bo'yicha
PEEK	`O(1)`	Ildiz doim indeks 0
Qurish (heapify)	`O(n)`	Barcha elementdan quyi qurish
Qidirish	`O(n)`	Tartibsiz axtarish

Nima uchun O(log n)? To'liq binar daraxt balandligi O(log n). Sift up va sift down ko'pi bilan balandlik qadam tashlaydi.

Nima uchun heapify O(n)? Bir qarashda n element uchun sift down — O(n log n) ko'rinadi. Lekin pastki qavat elementlari kam qadam tashlaydi (barg tugunlar 0 qadam). Amortizatsiyali tahlil O(n) ekanligini isbotlaydi.

Xotira: O(n) — massiv asosida, qo'shimcha pointer yo'q.

Heapify — massivdan heap qurish

Berilgan massivdan O(n) da heap qurish:

FUNCTION HEAPIFY(array)
    n = array hajmi

    // Barcha ichki tugunlardan oxirgisidan boshlab sift down
    FOR i = n/2 - 1 DAN 0 GACHA (kamayib)
        SIFT_DOWN(array, i, n)

    RETURN array   // endi heap

n/2 - 1 — oxirgi ichki tugun indeksi. Barglar (indeks n/2 dan n-1 gacha) sift down talab qilmaydi.

Boshlang'ich: [9, 5, 3, 7, 1]

i=1 (qiymat 5): left=3(7), right=4(1)
  smallest = 4 (1 < 5)
  almashtir: [9, 1, 3, 7, 5]
  i=1 ga sift down tugadi

i=0 (qiymat 9): left=1(1), right=2(3)
  smallest = 1 (1 < 3 < 9)
  almashtir: [1, 9, 3, 7, 5]
  i=1 ga tushdi: left=3(7), right=4(5)
    smallest = 4 (5 < 7 < 9)... aslida 5 < 7, 9 > 5 → almashtir
  [1, 5, 3, 7, 9]
  → BREAK

Natija: [1, 5, 3, 7, 9]   (min-heap)

K-ta eng kichik / eng katta element

Massivdan k-ta eng kichik elementni topish — heapning klassik qo'llanishi.

Yondashuv 1: barcha elementlardan min-heap quri, k marta POP qil. O(n + k log n).

Yondashuv 2: max-heap hajmini k da ushlab tur — k-ta eng kichikni saqlab yur.

FUNCTION K_SMALLEST(nums, k)
    heap = bo'sh max-heap   // hajmi k bilan cheklangan

    FOR har bir num ichida
        heap ga num PUSH

        IF heap hajmi > k
            heap dan POP   // eng kattasini chiqaramiz
            // heap'da doim k-ta eng kichik qoladi

    RETURN heap (yoki heap'dan k marta POP)

Vaqt: O(n log k) — har element uchun O(log k) push/pop.

Bu O(n log n) saralashdan yaxshiroq — k kichik bo'lganda.

Heap Sort

Heapdan saralash mumkin: barcha elementlardan max-heap qurib, n marta POP qilish. Natija o'sish tartibida.

FUNCTION HEAP_SORT(array)
    HEAPIFY(array)    // O(n), max-heap

    FOR i = n-1 DAN 1 GACHA
        array[0] va array[i] ni almashtir   // maksimumni oxiriga
        SIFT_DOWN(array, 0, i)              // qolgan [0, i-1] da heap tiklash

    RETURN array   // o'sish tartibida

Vaqt: O(n log n), xotira: O(1) (in-place).

Heap sort quicksort'ga qaraganda eng yomon holatda kafolatlanadi, lekin amalda cache miss'lar tufayli sekinroq ishlaydi.

Priority Queue misollari

Dijkstra algoritmi

Graf'da eng qisqa yo'lni topishda priority queue'dan eng kichik masofadagi tugunni olamiz.

Task scheduler

Operatsion tizim ustuvorlikli vazifalarni boshqarishda priority queue ishlatadi: eng yuqori ustuvorlikdagi jarayon birinchi bajariladi.

Merge k sorted arrays

k ta tartiblangan massivni birlashtirish: har massivning joriy elementini min-heap'ga qo'shamiz, POP qilganimizda eng kichik element keladi, keyin o'sha massivning keyingi elementini qo'shamiz.

FUNCTION MERGE_K_SORTED(arrays)
    heap = bo'sh min-heap   // (qiymat, massiv_indeksi, element_indeksi) tuples

    // Har massivning birinchi elementini qo'sh
    FOR i = 0 DAN k-1 GACHA
        IF arrays[i] bo'sh emas
            heap ga (arrays[i][0], i, 0) PUSH

    result = []

    WHILE heap bo'sh emas
        (val, arr_i, elem_i) = heap dan POP
        result ga val qo'sh

        next_elem_i = elem_i + 1
        IF next_elem_i < arrays[arr_i] hajmi
            heap ga (arrays[arr_i][next_elem_i], arr_i, next_elem_i) PUSH

    RETURN result

Vaqt: O(N log k) — N jami element, k massivlar soni.

Edge case'lar

Bo'sh heap'dan POP. Oldin bo'shligini tekshirish kerak. Aks holda indeks xatosi.

Bir xil ustuvorlikli elementlar. Heap xususiyati ≤ (teng ham bo'lishi mumkin). Teng ustuvorlikli elementlar orasidagi tartib kafolatlanmaydi — teng ustuvorlikli elementlarni FIFO tartibida qayta ishlash kerak bo'lsa, (ustuvorlik, kirish_vaqti) juftini saqlash kerak.

Bitta element. PUSH va POP to'g'ri ishlashi kerak: qo'shilsa, darhol POP qilib chiqarilishi kerak.

K = n. K ta eng kichik/katta — barcha elementlar. Heap yoki oddiy saralash teng samarali.

Note

Ko'p dasturlash tillarida built-in priority queue bor. Ular odatda min-heap. Max-heap kerak bo'lsa, qiymatlarni manfiy qilib qo'shish (-val) va chiqarganda manfiy qilish (-val) yoki tilning max-heap usulini ishlatish mumkin.

Heap va boshqa tuzilmalar taqqoslashi

Amal	Array	Sorted Array	BST	Heap
Min/Max topish	`O(n)`	`O(1)`	`O(log n)`	`O(1)`
Qo'shish	`O(1)`	`O(n)`	`O(log n)`	`O(log n)`
O'chirish min/max	`O(n)`	`O(n)`	`O(log n)`	`O(log n)`
Ixtiyoriy qidirish	`O(n)`	`O(log n)`	`O(log n)`	`O(n)`

Heap min/max'ni tez topish va tartibli qo'shish/o'chirish uchun moslashtirilgan. Ixtiyoriy elementni qidirish uchun mos emas.

Qachon heap ishlatish kerak?

Doimo eng kichik yoki eng katta elementni tezkor olish kerak bo'lganda.
K-ta eng kichik/katta elementni topish kerak bo'lganda.
K ta tartiblangan massivni birlashtirish kerak bo'lganda.
Dijkstra yoki Prim algoritmida qisqa bo'lim elementini tez olish kerak bo'lganda.
Ustuvorlikli navbat kerak bo'lganda.

Qachon heap ishlatmaslik kerak?

Ixtiyoriy elementni qidirish kerak bo'lsa — hash map yoki BST.
Tartibli traversal kerak bo'lsa — BST inorder beradi; heap to'liq tartib kafolatlamaydi.
Diapazon so'rovi kerak bo'lsa — BST samaraliroq.
Faqat stack yoki oddiy navbat kerak bo'lsa — heap keraksiz murakkablik.

Eng muhim xulosa

Heap to'liq binar daraxtni massivda saqlaydi. Min-heap'da ildiz doim eng kichik element — PEEK O(1). PUSH va POP O(log n) da sift up/down orqali bajariladi.

Priority queue heap asosida quriladi va "eng ustunini birinchi" tamoyilini O(log n) amallar bilan ta'minlaydi.

Heap uchun uchta asosiy savol: min yoki max kerak? Faqat minimum/maksimum kerakmi, yokin to'liq tartib? Kirish tartibi muhimmi (teng ustuvorlik uchun)? Bu savollarga javob heap tanlovini aniqlaydi.