Heap: min-heap va max-heap massivda — push, pop va heapify JavaScript'da

Qisqacha: Heap — eng kichik (min-heap) yoki eng katta (max-heap) elementni doim tepada tutadigan to'liq binar daraxt. U oddiy massivda saqlanadi: i-katakning bolalari 2i + 1 va 2i + 2 da, otasi (i − 1) ÷ 2 da. Eng kichigini ko'rish — O(1), qo'shish va olish — O(log n): element bitta yo'l bo'ylab yuqoriga yoki pastga suriladi. Tayyor massivdan heap yasash (heapify) — O(n). JavaScript'da tayyor heap yo'q — o'zingiz yozasiz.

Bu darsda

• Heap qoidasini va uning BST'dan farqini tushuntira olasiz.
• Daraxtni massivda saqlashning indeks formulalarini yoza olasiz.
• push (yuqoriga surish) va pop (pastga surish) ni yozasiz va qadamma-qadam kuzatasiz.
• Heapify nega O(n) ekanini tushuntirasiz va heap'ni saralangan va saralanmagan massiv bilan o'lchab solishtirasiz.

Oldin bilishingiz kerak: Daraxt atamalari va binar daraxt, Daraxt bo'ylab yurish: DFS va BFS, Binary Search Tree, Xotira murakkabligi, eng yomon holat va amortizatsiya.

1. Nega bu kerak?

«Bahor» oshxonasida buyurtmalar to'xtovsiz keladi. Har birida muddat bor: mehmon necha daqiqadan keyin taomini kutyapti. Oshpaz bitta qoida bilan ishlaydi: doim eng shoshilinch buyurtmani oladi. Kun davomida ikki amal aralash bajariladi: yangi buyurtma qo'shiladi va eng kichik muddatli buyurtma olinadi.

Sardor uch yechimni sinadi:

1. Saralanmagan massiv. Qo'shish — push, O(1). Eng kichigini olish — hammasini ko'rib chiqish, O(n).
2. Saralangan massiv. Eng kichigini olish — oxiridan pop, O(1). Qo'shish — to'g'ri joyga splice, O(n).
3. BST. Ikkalasi ham O(h), h — daraxt balandligi. Lekin muddatlar o'sib boruvchi tartibda kelsa, BST zanjirga aylanadi va h = n bo'lib qoladi. Balanslangan daraxt buni tuzatadi, ammo kodi og'ir.

Kun oxirida «Bahor»da 40 000 ga yaqin buyurtma o'tadi. Saralanmagan massivda har "eng shoshilinchini ol" butun ro'yxatni ko'radi — kun bo'yi jami 800 million solishtirish. O'lchovimizda bu taxminan 0,7 soniya CPU vaqti: bitta kassa uchun chidasa bo'ladi, lekin yuzlab filial bitta serverda ishlasa — yo'q.

Har birida bitta amal tez, ikkinchisi sekin. Bizga ikkala amal ham tez bo'lishi kerak. Lekin "hamma narsa tartibda" bo'lishi shart emas — faqat eng kichigi qayerdaligini bilish kifoya. Bugungi tuzilma aynan shu "yarim tartib" ni saqlaydi va shuning uchun arzon.

Diqqat: "Heap (uyum)" so'zi kursda ikki xil narsani bildiradi. Xotira boshqaruvi darsida u obyektlar yashaydigan xotira hududi edi, bu darsdan boshlab esa ma'lumotlar tuzilmasi — ular faqat nomdosh, bir-biriga aloqasi yo'q.

2. Heap qoidasi

2.1 Ta'rif

Heap (uyum) — ikki shartni bajaradigan binar daraxt:

1. Shakl: daraxt to'liq (Daraxt atamalari darsidagi ma'noda) — hamma qavatlar to'la, faqat oxirgisi chapdan o'ngga to'ladi, teshiksiz.
2. Tartib: har ota bolalaridan kichik yoki teng (min-heap). Max-heap'da aksincha — katta yoki teng.

Natija: eng kichik element doim ildizda. "Uyum" nomi shundan — uyulgan narsalarning eng yengili tepada.

          10
        /    \
      20      15
     /  \    /
   40    50 30

Tekshiring: 10 ≤ 20 va 15; 20 ≤ 40 va 50; 15 ≤ 30. Qoida bajariladi.

Heap qoidasini sport musobaqasiga o'xshatish mumkin. Kurash turnirida har juftlikdan g'olib yuqori bosqichga chiqadi. Final g'olibi — eng kuchlisi, bu aniq. Lekin ikkinchi o'rindagi kim? U albatta finalda yoki g'olibga yutqazganlar orasida — butun turnirni qaytadan o'tkazish shart emas. Heap ham shunday: "eng yaxshisi" tepada, qolganlar faqat "o'z guruhida" tartiblangan.

2.2 Heap — BST emas

BST'da "chap < ota < o'ng" — bu to'liq tartib: inorder saralangan ro'yxat beradi. Heap'da faqat "ota ≤ bolalar" — qo'shnilar orasida tartib yo'q. Yuqoridagi daraxtda 20 chapda, 15 o'ngda — BST'da bu mumkin emas edi. 40 ning 15 dan katta ekani ham daraxtdan ko'rinmaydi.

Heap kamroq va'da beradi. Ichidagi biror qiymatni qidirish — O(n), uni tez topish uchun hech qanday qoida yo'q. Eng kichigi esa doim ma'lum. Kam va'da — kam ish: shuning uchun heap BST'dan oddiyroq va tezroq.

Tekshirib ko'ring: [5, 8, 6, 9, 7] — bu massiv daraxt sifatida (i-katakning bolalari 2i + 1 va 2i + 2) min-heap'mi? Max-heap'mi?

3. Daraxt massivda

3.1 Indeks formulalari

Oldingi darslarda daraxt tuguni obyekt edi: { value, left, right }, bolalarga havola bilan. Heap uchun bunday tugunlar kerak emas. U har doim to'liq bo'lgani uchun uni havolalarsiz, oddiy massivda saqlash mumkin. Bolani havola emas, indeks formulasi topadi. Tugunlarni qavatma-qavat, chapdan o'ngga raqamlaymiz — xuddi level order tartibida:

indeks:   0   1   2   3   4   5
qiymat:  10  20  15  40  50  30

Uchta formula butun daraxtni beradi:

Belgi — pastga yaxlitlash, kodda Math.floor.

Formula qayerdan keladi? Kataklarni ketma-ket yozib ko'ring: 0-katakning bolalari — 1 va 2, 1-katakniki — 3 va 4, 2-katakniki — 5 va 6. Har ota ikkita bola "oladi", shuning uchun keyingi otaning bolalari ikki katak o'ngga suriladi: 2i. Boshida esa ildiz bor (0-katak) — shuning uchun + 1. Ota formulasi — shuning teskarisi. Tekshiramiz:

const heap = [10, 20, 15, 40, 50, 30];
const left = (i) => 2 * i + 1;
const right = (i) => 2 * i + 2;
const parent = (i) => Math.floor((i - 1) / 2);

console.log(heap[left(1)], heap[right(1)]); // 40 50
console.log(heap[parent(5)]); // 15
console.log(right(2) < heap.length); // false

Oxirgi qator: 2-katakning (15) o'ng bolasi 6-katakda bo'lardi, lekin massiv uzunligi 6 — demak, o'ng bola yo'q. Bola bor-yo'qligini doim shunday tekshiramiz: index < heap.length.

Massiv usulining afzalliklari: left, right havolalari yo'q — xotira tejaladi; elementlar xotirada yonma-yon — protsessor keshi ularni tez o'qiydi; yangi tugun yaratish shart emas.

Endi o'zingiz hisoblang. 100 elementli heap'da 49-katakning chap bolasi -katakda turadi.

3.2 Qavatlar soni

To'liq daraxtda balandlik — taxminan log₂ n. Million element — 20 qavat. Heap amallari bitta yo'l bo'ylab (ildizdan barggacha yoki aksincha) ishlaydi, shuning uchun ular O(log n). Daraxt hech qachon zanjirga aylanmaydi — shakl sharti buni ta'minlaydi. Burish yoki balans kerak emas.

4. Qo'shish: yuqoriga surish

Oshxonaga yangi buyurtma keldi. Oshpaz uni darrov "eng shoshilinch" deb qo'ya olmaydi — avval boshqalar bilan solishtirish kerak. Lekin hamma bilan emas: faqat o'zidan yuqoridagilar bilan, bittadan.

Yangi element qayerga qo'yiladi? Shakl buzilmasligi uchun — oxirgi qavatdagi birinchi bo'sh joyga, ya'ni massiv oxiriga. Lekin tartib buzilishi mumkin: yangi element otasidan kichik bo'lsa. Unda ota bilan almashtiramiz va yuqoriga chiqamiz. Ota kichik yoki teng bo'lguncha — yoki ildizga yetguncha. Bu yuqoriga surish (bubble up, sift up).

Nega faqat ota bilan solishtiramiz, qo'shni bola bilan emas? Ota allaqachon o'z bolalaridan kichik yoki teng. Yangi element otadan kichik bo'lsa, demak u qo'shnidan ham kichik. Almashtirgandan keyin qoida o'z-o'zidan saqlanadi.

Kuzating: muddatlar heap'iga 12 daqiqalik buyurtma qo'shiladi. Yuqorida — massiv, pastda — o'sha massiv daraxt ko'rinishida:

Almashtirish qatoriga qarang: [heap[parent], heap[i]] = [heap[i], heap[parent]]. Bu — destructuring bilan ikki katak qiymatini almashtirish, vaqtinchalik o'zgaruvchisiz (Massiv destructuring).

Eng yomon holatda yangi element ildizgacha ko'tariladi — log₂ n ta almashtirish. Tasodifiy ma'lumotda esa ko'pincha bir-ikki qavat yetadi: million tasodifiy son qo'shganda o'rtacha 1,3 ta almashtirish bo'ldi.

5. Eng kichigini olish: pastga surish

Eng kichigi — heap[0]. Peek (qarab qo'yish, olmasdan) — O(1). Uni olish esa qiyinroq: ildiz bo'shaydi, teshik paydo bo'ladi. Shaklni saqlash uchun oxirgi elementni olib, ildizga qo'yamiz. Endi tartib buzilgan: katta element tepada. Uni ikki bolasining kichigi bilan almashtiramiz va pastga tushamiz — ikkala boladan ham kichik bo'lguncha yoki barggacha. Bu pastga surish (bubble down, sift down).

Nega aynan kichik bola? Katta bola bilan almashtirsak, u tepaga chiqadi va kichik bola uning ostida qoladi — qoida buziladi. Kichigi tepaga chiqsa — u ikkinchi boladan ham kichik, qoida saqlanadi.

pop ham bitta yo'l bo'ylab tushadi: O(log n). Har qavatda ikkita solishtirish (ikki bola), shuning uchun u push dan biroz qimmatroq.

Tekshirib ko'ring: [3, 5, 4, 9, 6] min-heap'idan pop qilinsa, massiv qanday bo'ladi?

5.1 Max-heap

Ba'zan eng kattasi kerak: kunning eng qimmat buyurtmasi, eng ko'p kutgan mehmon. Max-heap — xuddi shu kod, faqat taqqoslash belgilari teskari: <= o'rniga >=, "kichik bola" o'rniga "katta bola". Kodni ikki marta yozmaslik uchun ikki usul bor.

Birinchisi — sonlar uchun hiyla: qiymatlarni minus bilan saqlash. Eng katta narx minus bilan eng kichik bo'ladi:

// max-heap: taqqoslash belgisini teskari qilish o'rniga — minus
const prices = [35000, 28000, 5000, 30000];
const heap = [];
function push(value) {
  heap.push(value);
  let i = heap.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (heap[parent] <= heap[i]) break;
    [heap[parent], heap[i]] = [heap[i], heap[parent]];
    i = parent;
  }
}
for (const price of prices) push(-price); // minus bilan saqlaymiz
console.log(-heap[0]); // 35000 — eng qimmati

Ikkinchisi — umumiyroq: heap'ga taqqoslovchi funksiya berish, xuddi sort ga berganimiz kabi. Shunda bitta klass min-heap ham, max-heap ham, obyektlar uchun heap ham bo'ladi. Buni keyingi darsda qilamiz: buyurtmalar obyekt bo'ladi va ularni muddat, keyin qo'shilish tartibi bo'yicha solishtiramiz.

5.2 Ixtiyoriy elementni o'zgartirish

Mehmon qo'ng'iroq qildi: "Buyurtmamni tezlashtiring, 10 daqiqada ketishim kerak." Heap ichidagi biror buyurtmaning muddatini kamaytirish kerak. Muammo — uni topish: heap'da qidirish O(n). Topilgandan keyin esa oson: qiymatni o'zgartirib, yuqoriga suramiz (muddat kamaygan bo'lsa) — O(log n).

Amalda ikki yo'l qo'llanadi. Birinchisi — qo'shimcha Map: "buyurtma raqami → heap'dagi indeks", har almashtirishda yangilanadi. Ikkinchisi — dangasa o'chirish (lazy deletion): eski yozuvni o'chirmaymiz, yangi muddat bilan yana bitta yozuv qo'shamiz. pop paytida eskirgan yozuv chiqsa — uni tashlab yuboramiz. Ikkinchisi oddiyroq va eng qisqa yo'l algoritmida aynan shunday ishlatiladi.

5.3 Oshxona kuni — hammasi birga

Endi push va pop ni aralash oqimda ishlatamiz. Buyurtmalar kelib turadi (son — muddat, daqiqa), oshpaz bo'shaganda esa eng shoshilinchini oladi:

function push(heap, value) {
  heap.push(value);
  let i = heap.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (heap[parent] <= heap[i]) break;
    [heap[parent], heap[i]] = [heap[i], heap[parent]];
    i = parent;
  }
}

function pop(heap) {
  const top = heap[0];
  const last = heap.pop();
  if (heap.length === 0) return top;
  heap[0] = last;
  let i = 0;
  while (true) {
    const l = 2 * i + 1;
    const r = l + 1;
    let s = i;
    if (l < heap.length && heap[l] < heap[s]) s = l;
    if (r < heap.length && heap[r] < heap[s]) s = r;
    if (s === i) return top;
    [heap[i], heap[s]] = [heap[s], heap[i]];
    i = s;
  }
}

// son — buyurtma keldi (muddati), "oshpaz" — oshpaz bo'shadi
const events = [25, 40, "oshpaz", 15, 30, "oshpaz", "oshpaz", 10,
  "oshpaz"];
const kitchen = [];
for (const event of events) {
  if (event === "oshpaz") {
    console.log(`Oshpaz oldi: ${pop(kitchen)} daq.`);
  } else {
    push(kitchen, event);
  }
}
console.log(`Navbatda qoldi: ${kitchen.join(", ")}`);

Konsolda:

Oshpaz oldi: 25 daq.
Oshpaz oldi: 15 daq.
Oshpaz oldi: 30 daq.
Oshpaz oldi: 10 daq.
Navbatda qoldi: 40

Natijaga diqqat bilan qarang. Birinchi oshpaz 25 ni oldi — o'sha paytda navbatda faqat 25 va 40 bor edi. 15 keyinroq keldi, lekin keyingi oshpaz uni darhol oldi, 40 ni "quvib o'tib". Oxirida kelgan 10 ham navbatda kutmadi. Oddiy navbat (Queue) kelish tartibida beradi, heap esa muhimlik tartibida. Aynan shu xususiyat keyingi darsda "ustuvor navbat" deb ataladi.

Tekshirib ko'ring: Shu kodda events oxiriga yana ikkita "oshpaz" qo'shilsa, nima chiqadi?

6. Heapify: tayyor massivdan heap

6.1 Ikki yo'l

Ertalab kassada 1 000 ta buyurtma allaqachon to'plangan. Ulardan heap yasash kerak. Birinchi yo'l — bittalab push: n ta amal, har biri O(log n), jami O(n log n). Ikkinchi yo'l — heapify: massivni joyida heap'ga aylantirish. Pastdan tepaga, oxirgi otadan boshlab ildizgacha har tugunni pastga suramiz.

Oxirgi ota qayerda? Massivning eng oxirgi elementi — n − 1-katak. Uning otasi — (n − 1 − 1) ÷ 2, ya'ni n ÷ 2 − 1. 6 elementli massivda bu 2-katak. Undan keyingi 3-, 4-, 5-kataklarning bolasi yo'q — ular barglar.

Nega pastdan boshlaymiz? Pastga surish bitta shart bilan ishlaydi: ota ostidagi ikki shox allaqachon heap bo'lishi kerak. Barglar o'z-o'zidan heap. Oxirgi otani tartibga keltirsak, uning shoxi heap bo'ladi. Keyingi ota uchun ham shart bajariladi — va shunday ildizgacha. Tepadan boshlasak, ostidagi shoxlar hali tartibsiz bo'lardi. Kuzating — 6 ta muddat:

Endi kod — vizualdagi bilan bir xil, ishga tushirib ko'ring:

function siftDown(heap, i) {
  while (true) {
    const left = 2 * i + 1;
    const right = left + 1;
    let smallest = i;
    if (left < heap.length && heap[left] < heap[smallest]) {
      smallest = left;
    }
    if (right < heap.length && heap[right] < heap[smallest]) {
      smallest = right;
    }
    if (smallest === i) return;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
}

function heapify(values) {
  // barglar (ikkinchi yarmi) allaqachon heap — ulardan boshlamaymiz
  for (let i = Math.floor(values.length / 2) - 1; i >= 0; i--) {
    siftDown(values, i);
  }
  return values;
}

console.log(heapify([50, 40, 30, 20, 10, 15]).join(" "));

Konsolda:

10 20 15 50 40 30

siftDown — pop ichidagi pastga surishning o'zi, alohida funksiyaga chiqarilgan. Sikl esa uni oxirgi otadan ildizgacha har bir ota uchun bir martadan chaqiradi. Har ota ostidagi ikki shox allaqachon heap bo'lgani uchun bitta pastga surish yetadi.

6.2 Nega O(n)?

Bir qarashda: n ÷ 2 ta ota, har biri log n gacha tushadi — O(n log n). Lekin ko'pchilik otalar pastda turadi va qisqa yo'l bosadi:

Jami: n ÷ 4 · 1 + n ÷ 8 · 2 + n ÷ 16 · 3 + … Bu yig'indi n dan oshmaydi. Uzun yo'l bosadiganlar kam, ko'pchilik esa deyarli joyidan qimirlamaydi.

Kichik misolda sanab ko'ramiz. 15 elementli to'liq daraxtda 4 qavat bor. Barglar — 8 ta, ular umuman yurmaydi. Ulardan yuqoridagi 4 ta ota ko'pi bilan 1 qadam tushadi — jami 4. Keyingi 2 ta ota ko'pi bilan 2 qadamdan — jami 4. Ildiz ko'pi bilan 3 qadam. Hammasi: 4 + 4 + 3 = 11 qadam, ya'ni 15 dan kam. Bittalab push da esa har element o'z qavatigacha ko'tarilishi mumkin: 2 · 1 + 4 · 2 + 8 · 3 = 34 qadamgacha. Ko'pchilik element pastda turadi — push da ular eng uzun yo'lni bosadi, heapify da esa umuman yurmaydi. Sanadik — kamayuvchi tartibdagi million sonda (eng yomon kirish):

push bilan — 18 marta ko'p almashtirish va 8 baravar ko'p vaqt. Tasodifiy sonlarda farq kichikroq (push ham o'rtacha qisqa yo'l bosadi): 2 million sonda 59 ms va 26 ms. Ikkala usulda ham n ikki baravar — vaqt ikki baravar: ma'lumot tasodifiy bo'lsa, push amalda chiziqli ishlaydi, heapify esa har qanday kirishda O(n).

7. Murakkablik va o'lchov

Xotira: hammasi O(n), heap — oddiy massiv, qo'shimcha joysiz.

Oshxona ssenariysini o'lchadik: n ta buyurtma qo'shiladi, keyin hammasi "eng shoshilinchi birinchi" tartibida olinadi:

Nega natijalar shunday? Heap har amalda log₂ n qavatdan ko'p yurmaydi: 40 000 elementda — 16 qavat. Saralanmagan massiv har pop da qolgan hamma elementni ko'radi — o'rtacha 20 000 ta. Saralangan massivda esa splice har qo'shishda o'rtacha yarim massivni suradi. U ham O(n), lekin xotirani bir bo'lak qilib ko'chirish juda tez — shuning uchun u saralanmagan massivdan 14 baravar oldinda.

Heap: n ikki baravar — vaqt ×2,1–2,3 (n log n). Ikkala massiv: ×4 (n²). Saralangan massiv splice tufayli kichik n da heap bilan yaqin, lekin 40 000 da 9 baravar orqada. Heap'ni kattaroq n da ham o'lchadik: million buyurtma — ≈ 196 ms.

Maslahat: Agar hamma buyurtmalar oldindan ma'lum bo'lsa va yangisi qo'shilmasa — bir marta toSorted yetarli (O(n log n)). Heap'ning kuchi aralash oqimda: qo'shish va olish navbatma-navbat keladi.

8. Heap sort

Heap bilan saralash ham mumkin. Massivni max-heap'ga aylantiramiz (O(n)). Keyin n marta eng kattasini (ildizni) massiv oxiridagi element bilan almashtiramiz va heap chegarasini bittaga qisqartiramiz. Massiv oxiridan boshlab saralangan qism o'sib boradi:

function heapSort(values) {
  const a = [...values];
  // max-heap uchun pastga surish: "eng katta bola" bilan
  function down(i, size) {
    while (true) {
      const left = 2 * i + 1;
      const right = left + 1;
      let largest = i;
      if (left < size && a[left] > a[largest]) largest = left;
      if (right < size && a[right] > a[largest]) largest = right;
      if (largest === i) return;
      [a[i], a[largest]] = [a[largest], a[i]];
      i = largest;
    }
  }
  for (let i = Math.floor(a.length / 2) - 1; i >= 0; i--) {
    down(i, a.length); // 1) max-heap — O(n)
  }
  for (let end = a.length - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]]; // 2) eng kattasi oxiriga
    down(0, end); // heap bittaga qisqardi
  }
  return a;
}

console.log(heapSort([35, 28, 5, 30, 12, 28]).join(" "));

Konsolda:

5 12 28 28 30 35

down ikkinchi parametr — size — oladi: heap massivning faqat boshidagi size ta katakda. Oxiridagilar allaqachon saralangan va ularga tegilmaydi. Natija — heap sort: O(n log n) har qanday kirishda, qo'shimcha xotirasiz (joyida). Kamchiliklari: barqaror emas (Saralash tushunchalari) va amalda merge sort yoki TimSort'dan sekinroq — elementlar xotirada uzoq sakraydi. Shuning uchun u kam ishlatiladi, lekin intervyularda so'raladi.

9. Chegaraviy holatlar

• Bo'sh heap. peek va pop — undefined. pop ichida birinchi tekshiruv shuning uchun.
• Bitta element. pop uni oladi va massiv bo'shaydi. Shundan keyin "oxirgisini tepaga qo'yish" kerak emas — aks holda olingan element qaytib joyiga yoziladi. Shuning uchun koddagi ikkinchi tekshiruv: if (heap.length === 0) return top;.
• Takroriy qiymatlar. Qoida "kichik yoki teng" — takrorlar muammo emas. Lekin heap barqaror emas: teng muddatli ikki buyurtma qaysi tartibda chiqishi kafolatlanmaydi. Kerak bo'lsa, qo'shilish raqamini ikkinchi kalit qiling (keyingi darsda).
• Manfiy sonlar. Hech qanday farqi yo'q.

10. Ko'p uchraydigan xatolar

10.1 Formula: 2i + 1 va 2i

1 dan boshlab raqamlangan kitoblarda bolalar 2i va 2i + 1, ota i ÷ 2. JavaScript massivi 0 dan boshlanadi — 2i + 1, 2i + 2 va (i − 1) ÷ 2. Aralashtirilsa, kod xatosiz ishlaydi, lekin heap jimgina buziladi. Tuzatish: 0-katak bolalari 1 va 2 ekanini tekshiring.

10.2 Pastga surishda katta bola bilan almashtirish

Birinchi topilgan "kichikroq" bola bilan almashtirish — xato. Ikkala bolani ham solishtiring va eng kichigini tanlang.

10.3 Heap'ni saralangan deb o'ylash

console.log(heap) — [10, 20, 15, 40, 50, 30]. Bu saralangan emas! Saralangan tartibni olish uchun n marta pop qiling. Tuzatish: heap massivining ichki tartibiga tayanmang — faqat peek va pop orqali ishlang.

10.4 sort bilan "heap"

Har qo'shishdan keyin array.sort() — O(n log n) har safar. Heap'ning ma'nosi yo'qoladi.

11. Mashqlar

1-mashq (oson): Formulalar

[2, 7, 4, 9, 8, 5] massivi berilgan. Daraxtini chizing. 7 ning bolalari kimlar? 5 ning otasi kim? Bu min-heap'mi?

        2
      /   \
     7     4
    / \   /
   9   8 5

2-mashq (o'rta): Heap'mi?

isMinHeap(array) funksiyasini yozing: massiv min-heap qoidasini bajarsa true. Ishora: har ota uchun (every ham mumkin, oddiy sikl ham) uning bolalarini tekshiring; faqat birinchi yarmini ko'rish yetadi.

function isMinHeap(a) {
  for (let i = 0; 2 * i + 1 < a.length; i++) {
    const left = 2 * i + 1;
    const right = left + 1;
    if (a[left] < a[i]) return false;
    if (right < a.length && a[right] < a[i]) return false;
  }
  return true;
}

console.log(isMinHeap([2, 7, 4, 9, 8, 5])); // true
console.log(isMinHeap([5, 8, 6, 9, 4])); // false
console.log(isMinHeap([])); // true

3-mashq (qiyin): MinHeap klassi va testlar

kurs/mashqlar/14/42-heap/heap.test.mjs faylida MinHeap klassini yozing: yashirin #items massivi, size, peek, push, pop va statik MinHeap.from(values) — heapify bilan (asl massivni o'zgartirmasin). Yordamchi drain(heap) — hamma elementni pop bilan olib, massivga yig'adi. Testlar (node:test): bo'sh heap; takrorlar va manfiy sonlar; from natijasi toSorted bilan bir xil; push va pop aralash.

// kurs/mashqlar/14/42-heap/heap.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

class MinHeap {
  #items = [];

  static from(values) {
    const heap = new MinHeap();
    heap.#items = [...values];
    // oxirgi otadan ildizgacha — har birini pastga tushiramiz
    for (let i = Math.floor(heap.size / 2) - 1; i >= 0; i--) {
      heap.#down(i);
    }
    return heap;
  }
  get size() {
    return this.#items.length;
  }
  peek() {
    return this.#items[0];
  }
  push(value) {
    const a = this.#items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (a[parent] <= a[i]) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }
  pop() {
    const a = this.#items;
    if (a.length === 0) return undefined;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      this.#down(0);
    }
    return top;
  }
  #down(i) {
    const a = this.#items;
    while (true) {
      const left = 2 * i + 1;
      const right = left + 1;
      let smallest = i;
      const n = a.length;
      if (left < n && a[left] < a[smallest]) smallest = left;
      if (right < n && a[right] < a[smallest]) smallest = right;
      if (smallest === i) return;
      [a[i], a[smallest]] = [a[smallest], a[i]];
      i = smallest;
    }
  }
}

function drain(heap) {
  const out = [];
  while (heap.size > 0) out.push(heap.pop());
  return out;
}

test("bo'sh heap", () => {
  const h = new MinHeap();
  assert.equal(h.pop(), undefined);
  assert.equal(h.peek(), undefined);
  assert.equal(h.size, 0);
});

test("push/pop — o'sish tartibida, takrorlar bilan", () => {
  const h = new MinHeap();
  for (const v of [30, 10, 50, 10, -5, 20]) h.push(v);
  assert.equal(h.peek(), -5);
  assert.deepEqual(drain(h), [-5, 10, 10, 20, 30, 50]);
});

test("from (heapify) — push bilan bir xil natija", () => {
  const values = Array.from({ length: 1000 }, (_, i) => i * 7919);
  for (let i = 0; i < values.length; i++) values[i] %= 1000;
  const sorted = values.toSorted((a, b) => a - b);
  assert.deepEqual(drain(MinHeap.from(values)), sorted);
  assert.equal(values[0], 0); // asl massiv o'zgarmadi
  assert.equal(values[1], 919);
});

test("push va pop aralash", () => {
  const h = MinHeap.from([40, 15]);
  h.push(5);
  assert.equal(h.pop(), 5);
  h.push(25);
  assert.deepEqual(drain(h), [15, 25, 40]);
});

✔ bo'sh heap (0.7355ms)
✔ push/pop — o'sish tartibida, takrorlar bilan (0.7853ms)
✔ from (heapify) — push bilan bir xil natija (3.3277ms)
✔ push va pop aralash (0.1877ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 93.0765

4-mashq: Amaliy tajriba — heap qatorlari

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: heap peek, push, pop, heapify, heap sort. "Eng kichigini olish" masalasi uchun uchta yechimni yonma-yon yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Eng kichigini ko'rish | heap peek | O(1) | O(1) |
| Qo'shish | heap push | O(log n) | O(1) amort. |
| Eng kichigini olish | heap pop | O(log n) | O(1) |
| Eng kichigini olish | saralanmagan massiv | O(n) | O(1) |
| Heap yasash | heapify | O(n) | O(1) joyida |
| Saralash | heap sort | O(n log n) | O(1), barqaror emas |

git add 14/MURAKKABLIK.md 14/42-heap
git commit -m "14/42: MinHeap — push, pop, heapify"

12. Real ishda

• Rejalashtiruvchilar. Operatsion tizimlar va Node.js'ning taymerlari "eng yaqin muddatli vazifa" ni topish uchun heap'ga o'xshash tuzilmalardan foydalanadi. setTimeout lar ko'p bo'lsa ham, keyingisi tez topiladi.
• Graf algoritmlari. Eng qisqa yo'l (Dijkstra) har qadamda "eng yaqin hali ko'rilmagan tugun" ni oladi — heap bilan.
• Ma'lumotlar bazalari. Indeks bo'lmasa, PostgreSQL ORDER BY narx LIMIT 10 so'rovi uchun butun jadvalni saralamaydi. U "top-N heapsort" usulini tanlaydi — xotirada faqat 10 ta qatorli heap ushlaydi. EXPLAIN ANALYZE chiqishida buni "Sort Method: top-N heapsort" qatori ko'rsatadi; bu buyruqni 26-qismda o'rganamiz.
• Top-K va oqimlar. "Eng ko'p sotilgan 10 taom", "oqim medianasi" — keyingi dars mavzusi.
• JavaScript. Tilda tayyor heap yoki priority queue yo'q (Python'da heapq, Java'da PriorityQueue bor). Intervyuda o'zingiz yozasiz — shuning uchun bu darsdagi MinHeap ni yod bilishga arziydi.

Xulosa

• Heap — to'liq binar daraxt, har ota bolalaridan kichik yoki teng (min-heap); eng kichigi doim ildizda. Bu BST emas — qo'shnilar orasida tartib yo'q.
• Massivda: bolalar 2i + 1 va 2i + 2, ota (i − 1) ÷ 2. Havolalar kerak emas.
• push — oxiriga qo'yib yuqoriga surish, pop — oxirgisini tepaga qo'yib, kichik bola bilan pastga surish: ikkalasi O(log n); peek — O(1).
• Heapify — pastdan tepaga pastga surish, O(n): kamayuvchi million sonda 1 mln almashtirish, bittalab push da 18 mln.
• O'lchov: 40 000 ta qo'shish + olish — heap ≈ 5,7 ms, saralanmagan massiv ≈ 681 ms.

Keyingi dars: Priority queue va heap naqshlari — obyektlar va taqqoslovchi bilan navbat, top-K, k ta saralangan ro'yxatni birlashtirish va ikki heap bilan mediana.

Manbalar

• J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM, 1964 — heap va heap sort.
• Robert W. Floyd, "Algorithm 245: Treesort 3", Communications of the ACM, 1964 — O(n) heapify.
• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 6-bob (heapsort, priority queues).