3.8-bob: Heap (priority queue)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 8-mavzu

1. Kirish va motivatsiya

Queue 3.4-bob — FIFO (kelish tartibida) edi. Lekin ba'zan element kelish tartibida emas, muhimligi (priority) bo'yicha chiqishi kerak: kasalxona shoshilinch xonasi (og'ir bemor birinchi, navbat emas), task scheduler (yuqori muhimlikli vazifa), Dijkstra (3.7: eng kam masofali tugun).

Buni amalga oshirish uchun har safar massivni saralash — O(n log n) 3.9-bob. Heap esa eng katta (yoki kichik) elementni O(log n) da, eng katta/kichikni ko'rishni O(1) da beradi — ancha samarali. Heap — Priority Queue ning eng yaxshi amalga oshirilishi.

O'xshatish: heap — kasalxona shoshilinch navbati. Yangi bemor kelganda — navbat oxiriga emas, holatiga qarab joylashtiriladi. Shifokor doim eng og'ir bemorni oladi (priority). Lekin to'liq saralash shart emas — faqat "eng og'iri kim?" muhim. Heap aynan shuni tez qiladi.

Nega muhim?

• Priority Queue — Dijkstra 3.7-bob, task scheduler, rate limiting.
• Top-K masalalari — "eng katta K element", "eng ko'p uchragan K" 3.2-bob — heap bilan samarali.
• Heap sort 3.9-bob — O(n log n) saralash.
• Real: OS process scheduler, event-driven tizimlar, media stream buffer.

2. Nazariya — chuqur tushuntirish

2.1. Heap nima?

Heap — maxsus binary tree 3.6-bob, ikki qoidaga bo'ysunadi:

1. Heap qoidasi (heap property):
   • Min-heap: har node o'z bolalaridan kichik yoki teng (ildiz — eng kichik).
   • Max-heap: har node o'z bolalaridan katta yoki teng (ildiz — eng katta).
2. To'liq daraxt (complete tree): barcha darajalar to'la, oxirgisi chapdan to'ldirilgan.

  Max-heap:              Min-heap:
        100                    1
       /   \                 /   \
      19    36              5     3
     / \   / \            / \   / \
    17  3 25  1          17 10 8  4

  Har ota >= bolalar     Har ota <= bolalar

Heap — BST emas 3.6-bob! BST'da chap < node < o'ng (qat'iy tartib). Heap'da faqat ota-bola munosabati (ildiz eng katta/kichik), aka-uka orasida tartib yo'q. Heap "eng katta/kichik kim?" ga javob beradi, "saralangan ro'yxat"ga emas.

2.2. Heap — massivda saqlanadi (sirq)

Heap to'liq daraxt bo'lgani uchun, node/pointer'siz, oddiy massivda saqlanadi (3.6: pointer kerak emas). Indeks formulalari:

  Massiv:  [100, 19, 36, 17, 3, 25, 1]
  Indeks:    0    1   2   3  4   5   6

  i-indeksdagi node uchun:
    ota:        (i - 1) / 2  (butun)
    chap bola:  2i + 1
    o'ng bola:  2i + 2

  Indeks 1 (19): ota = 0 (100), chap = 3 (17), o'ng = 4 (3)

Nega massiv? To'liq daraxt — "teshiksiz", shuning uchun darajalarni massivga ketma-ket joylash mumkin. Bu — xotira tejash (pointer yo'q) va tez murojaat (indeks O(1) — 3.2).

2.3. Insert (qo'shish) — "bubble up" — O(log n)

Yangi element oxirga qo'shiladi, keyin heap qoidasi buzilmaguncha yuqoriga "ko'tariladi" (otasi bilan almashadi):

  Max-heap'ga 50 qo'shish:
  1. Oxirga qo'sh:  [100, 19, 36, ..., 50]
  2. Otasi bilan solishtir: 50 > otasi?  almash (bubble up)
  3. Joyiga yetguncha takrorla (eng ko'pi balandlik = log n marta)

insert(value) {
  this.heap.push(value);              // oxirga (3.2: O(1))
  this.bubbleUp(this.heap.length - 1);
}
bubbleUp(i) {
  while (i > 0) {
    const ota = Math.floor((i - 1) / 2);   // (2.2)
    if (this.heap[i] <= this.heap[ota]) break;   // max-heap: joyida
    [this.heap[i], this.heap[ota]] = [this.heap[ota], this.heap[i]];  // almash (2.8)
    i = ota;                            // yuqoriga
  }
}
// O(log n) — balandlik bo'yicha

2.4. Extract (eng katta/kichikni olish) — "bubble down" — O(log n)

Ildiz (eng katta/kichik) olinadi, oxirgi element ildizga qo'yiladi, keyin pastga "tushadi":

  Max-heap'dan max (100) olish:
  1. Ildiz (100) ni ol (natija)
  2. Oxirgi elementni ildizga qo'y
  3. Kattaroq bola bilan solishtir: kichik bo'lsa  almash (bubble down)
  4. Joyiga yetguncha takrorla

extractMax() {
  if (this.heap.length === 0) return undefined;   // bo'sh (0.6)
  const max = this.heap[0];                        // ildiz — eng katta
  const oxirgi = this.heap.pop();
  if (this.heap.length > 0) {
    this.heap[0] = oxirgi;            // oxirgini ildizga
    this.bubbleDown(0);
  }
  return max;
}
// O(log n)

2.5. Peek — eng katta/kichikni ko'rish — O(1)

peek() { return this.heap[0]; }   // ildiz — olmasdan ko'rish, O(1)

2.6. Murakkablik va Queue/BST bilan taqqoslash

Heap'ning kuchi: min/max'ga doimiy tez murojaat (peek O(1), extract O(log n)). Cheklovi: ixtiyoriy elementni qidirish sekin (O(n)) — heap "saralangan" emas, faqat "eng yaxshi" ni biladi 2.1-bob.

2.7. Priority Queue

Priority Queue — elementlar muhimlik bilan; eng muhim birinchi chiqadi. Heap — uning standart amalga oshirilishi:

// Element: { value, priority }
pq.enqueue("oddiy task", 1);
pq.enqueue("shoshilinch", 10);
pq.dequeue();   // "shoshilinch" (eng yuqori priority — FIFO emas!)

Qo'llanishlar: Dijkstra 3.7-bob, OS scheduler, event simulyatsiyasi, A* qidiruv (o'yinlar).

2.8. Top-K naqshi (heap qo'llanishi)

"Eng katta K element" — butun massivni saralash (O(n log n) — 3.9) o'rniga, K hajmli heap (O(n log K)):

  Eng katta 3 element topish (min-heap, hajm 3):
  - Heap'ga qo'sh; hajm > 3 bo'lsa, eng kichikni (ildiz) chiqar
  - Oxirida heap'da eng katta 3 element qoladi

Bu — katta ma'lumotda samarali (butun saralashdan tez, K kichik bo'lsa).

2.9. Heapify va build-heap — tayyor massivdan heap qurish — O(n)

Heapify — heap qoidasini tiklash amali; uning ikki yo'nalishi bor:

• Sift up (yuqoriga surish) — bu bizning bubble up 2.3-bob: element otasi bilan almashib yuqoriga ko'tariladi.
• Sift down (pastga surish) — bu bizning bubble down 2.4-bob: element kattaroq/kichikroq bola bilan almashib pastga tushadi.

Ya'ni "bubble up/down" — heapify'ning ikki ko'rinishi (atama: turli kitobda turlicha — sift/bubble/percolate, mohiyat bir xil).

Build-heap — tartibsiz massivni butunlay heap'ga aylantirish. Ikki yo'l bor:

  YO'L 1 (sodda): har elementni navbat bilan insert qil
     n marta bubble up  O(n log n)

  YO'L 2 (Floyd build-heap, tez): massivni joyida heapify qil
    - Oxirgi ota indeksidan boshlab orqaga yur:  i = (n/2 - 1) ... 0
    - Har node uchun bubble down (sift down)
     O(n) (har emas, balki barg yaqinidagilar arzon)

buildHeap(arr) {
  this.heap = arr;
  for (let i = (arr.length >> 1) - 1; i >= 0; i--) {  // oxirgi otadan orqaga
    this.bubbleDown(i);                                // sift down (2.4)
  }
}
// O(n) — har element O(log n) emas, chunki ko'pchilik node barg yaqinida (arzon)

Nega O(n), O(n log n) emas? Bargdagi node'lar (yarmi) — 0 qadam tushadi, ulardan yuqoridagilar kamroq. Yig'indi qator O(n) ga teng (3.1: amortizatsiya mantig'i). Bu — n marta insert (O(n log n)) dan tez: heap sort va Dijkstra 3.7-bob shu qurilishdan foyda oladi.

3. Sintaksis — tez ma'lumotnoma

HEAP QOIDASI:  min-heap (ildiz eng kichik) / max-heap (ildiz eng katta)
SAQLASH:       massivda (pointer yo'q); ota=(i-1)/2, bola=2i+1, 2i+2
INSERT:        oxirga + bubble up — O(log n)
EXTRACT:       ildizni ol + oxirgini yuqoriga + bubble down — O(log n)
PEEK:          ildiz — O(1)
BUILD-HEAP:    massivni heapify (oxirgi otadan sift down) — O(n)
PRIORITY QUEUE: heap ustida; eng muhim birinchi
TOP-K:         K hajmli heap — O(n log K)

4. Batafsil kod namunalari

Misol 1 — Min-Heap (to'liq — 2.3, 2.4)

class MinHeap {
  constructor() { this.heap = []; }

  peek() { return this.heap[0]; }                  // O(1) (2.5)
  get size() { return this.heap.length; }

  insert(value) {                                   // O(log n) (2.3)
    this.heap.push(value);
    let i = this.heap.length - 1;
    while (i > 0) {
      const ota = (i - 1) >> 1;                     // (2.2)
      if (this.heap[i] >= this.heap[ota]) break;    // min-heap: joyida
      [this.heap[i], this.heap[ota]] = [this.heap[ota], this.heap[i]];
      i = ota;
    }
  }

  extractMin() {                                    // O(log n) (2.4)
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const oxirgi = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = oxirgi;
      this.bubbleDown(0);
    }
    return min;
  }

  bubbleDown(i) {
    const n = this.heap.length;
    while (true) {
      let kichik = i;
      const chap = 2 * i + 1, ong = 2 * i + 2;       // (2.2)
      if (chap < n && this.heap[chap] < this.heap[kichik]) kichik = chap;
      if (ong < n && this.heap[ong] < this.heap[kichik]) kichik = ong;
      if (kichik === i) break;                        // joyida
      [this.heap[i], this.heap[kichik]] = [this.heap[kichik], this.heap[i]];
      i = kichik;
    }
  }
}

const h = new MinHeap();
[5, 3, 8, 1, 9, 2].forEach(x => h.insert(x));
console.log(h.peek());        // 1 (eng kichik — O(1))
console.log(h.extractMin());  // 1
console.log(h.extractMin());  // 2 (keyingi eng kichik)

Misol 2 — Priority Queue (muhimlik bilan — 2.7)

class PriorityQueue {
  constructor() { this.heap = []; }   // { value, priority }

  enqueue(value, priority) {
    this.heap.push({ value, priority });
    let i = this.heap.length - 1;
    while (i > 0) {
      const ota = (i - 1) >> 1;
      if (this.heap[i].priority <= this.heap[ota].priority) break;  // max-priority
      [this.heap[i], this.heap[ota]] = [this.heap[ota], this.heap[i]];
      i = ota;
    }
  }
  // dequeue() — extractMax mantiqi (eng yuqori priority)
}

const pq = new PriorityQueue();
pq.enqueue("Email yuborish", 1);
pq.enqueue("Server o'chdi!", 10);    // yuqori priority
pq.enqueue("Hisobot", 5);
// dequeue  "Server o'chdi!" (priority 10 — FIFO emas)

Misol 3 — Top-K (eng katta K — 2.8)

// Eng katta K element (min-heap hajm K bilan — O(n log K))
function topK(arr, k) {
  const heap = new MinHeap();
  for (const x of arr) {
    heap.insert(x);
    if (heap.size > k) heap.extractMin();   // eng kichikni chiqar (K saqlanadi)
  }
  const natija = [];
  while (heap.size) natija.push(heap.extractMin());
  return natija.reverse();   // eng katta K (kamayish)
}
topK([3, 1, 5, 12, 2, 11], 3);   // [12, 11, 5]
// Butun saralash O(n log n) o'rniga O(n log K) — K kichik bo'lsa tez

Misol 4 — Heap sort (3.9 ga ko'prik)

// Heap bilan saralash — O(n log n) (3.9)
function heapSort(arr) {
  const heap = new MinHeap();
  for (const x of arr) heap.insert(x);    // O(n log n)
  const tartiblangan = [];
  while (heap.size) tartiblangan.push(heap.extractMin());  // eng kichikdan
  return tartiblangan;
}
heapSort([5, 2, 8, 1, 9]);   // [1, 2, 5, 8, 9]
// Tezroq: qurishni build-heap (O(n) — 2.9) bilan boshlash mumkin; umumiy baribir O(n log n) (extract bosqichi).

5. To'g'ri va noto'g'ri holatlar

1) Min/max uchun har safar saralash

//  har safar butun massivni saralash — O(n log n) (3.9)
arr.sort((a, b) => a - b)[0];   // eng kichik uchun

//  heap — extract O(log n), peek O(1) (2.6)
heap.extractMin();

2) Heap'da ixtiyoriy element qidirish

 heap saralangan emas — qidiruv O(n) (2.6)
 qidiruv kerak bo'lsa — BST/Hash Table (3.5, 3.6); heap faqat min/max uchun

3) Bubble up/down'ni unutish

//  faqat push/pop — heap qoidasi buziladi (2.3, 2.4)
this.heap.push(x);   // bubble up yo'q!

//  qoidani tiklash
this.heap.push(x); this.bubbleUp(...);

4) Bo'sh heap'da extract

//  bo'shda extract  undefined, keyin xato (0.6)
const min = heap.extractMin().value;

//  tekshir
if (heap.size) { const min = heap.extractMin(); }

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Heap qoidasi buzilgan (noto'g'ri natija)

Sababi: insert/extract'da bubble up/down to'liq emas (2.3, 2.4). Yechimi: har amal'dan keyin qoida tiklanishini tekshiring; kichik misolda qo'lda yuring 0.6-bob.

Xato 2 — Indeks formulasi xato

Sababi: ota/bola indeks formulasi noto'g'ri (2i+1, (i-1)/2 — 2.2). Yechimi: formulani aniq yozing; chegara (chap < n) tekshiring.

Xato 3 — Cannot read properties of undefined

Sababi: bo'sh heap yoki chegaradan tashqari indeks (0.6, 4-holat). Yechimi: size tekshiring; chap < n && ong < n.

Xato 4 — Min-heap o'rniga max-heap (yoki teskari)

Sababi: taqqoslash yo'nalishi xato (< vs > — 2.3). Yechimi: min-heap: ildiz eng kichik (<); max-heap: eng katta (>).

Xato 5 — Sekin (heap o'rniga noto'g'ri tuzilma)

Sababi: priority/top-K uchun saralash yoki linear qidiruv (1-holat). Yechimi: heap — O(log n) extract.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Queue 3.4-bob: Priority Queue — heap ustida (FIFO emas, muhimlik).
• Graph/Dijkstra 3.7-bob: eng kam masofali tugun — min-heap.
• Tree 3.6-bob: heap — to'liq binary tree (lekin BST emas).
• Saralash 3.9-bob: heap sort — O(n log n).
• Massiv algoritmlari 3.2-bob: top-K, eng ko'p uchragan K.
• Big-O 3.1-bob: heap — log n amallar.
• Real: OS scheduler, task queue 5.22-bob, event simulyatsiya, media buffer.

8. Eng yaxshi amaliyotlar (best practices)

• Min/max'ga tez-tez murojaat heap (peek O(1), extract O(log n)), saralash emas 2.6-bob.
• Priority kerak Priority Queue (heap), oddiy Queue emas (2.7, 3.4).
• Top-K K hajmli heap (O(n log K)) — butun saralashdan tez 2.8-bob.
• Massivda saqlash — pointer'siz, formulalar bilan 2.2-bob.
• Bubble up/down — har insert/extract'da qoidani tiklash (2.3, 2.4).
• Tayyor massivdan heap build-heap (O(n) — 2.9), n marta insert (O(n log n)) emas.
• Heap'da qidiruv qilmang (O(n)) — min/max uchun ishlating 2.6-bob.
• Bo'sh holatni tekshiring (size) extract/peek'dan oldin (6-bo'lim).
• JS'da tayyor heap yo'q — o'zingiz yozing yoki kutubxona (@datastructures-js/priority-queue); kunlik ishda kamroq, lekin Dijkstra/top-K uchun zarur.

9. Amaliy loyiha: "Priority Queue va Top-K Tizimi"

Heap va uning qo'llanishlarini amalda mustahkamlash — 3-QISMning yarmi yakuni.

Maqsad

Min/Max heap qurib, Priority Queue, top-K va heap sort algoritmlarini qo'llash; heap qoidasini va indeks mexanizmini tushunish.

Talablar (requirements)

1. MinHeap class: insert, extractMin, peek, size — bubble up/down bilan (Misol 1).
2. MaxHeap class: xuddi shu, lekin teskari (yoki bitta heap'ga komparator — bonus).
3. Priority Queue: {value, priority} bilan; enqueue/dequeue muhimlik bo'yicha (Misol 2, 2.7).
4. Top-K: massivdan eng katta K va eng kichik K element (Misol 3, 2.8).
5. Heap sort: massivni heap bilan saralang (Misol 4); Big-O ni ayting 3.1-bob.
6. Median stream (bonus): ikki heap bilan oqimdagi medianani topish (klassik).
7. Task scheduler (amaliy): Priority Queue bilan vazifalarni muhimlik bo'yicha bajarish.
8. Chegaraviy holatlar: bo'sh heap, bitta element, teng priority 0.6-bob.
9. Har amal Big-O bilan; saralash bilan solishtiring (qaysi tezroq va qachon — 3.1).

Maslahatlar (hint)

• Indeks: ota (i-1)>>1, bola 2i+1/2i+2 2.2-bob.
• Insert: oxirga push + bubble up; extract: ildizni ol + oxirgini yuqoriga + bubble down.
• Min vs max — taqqoslash yo'nalishi (< vs > — 4-holat).
• Top-K: min-heap hajm K (eng katta uchun); hajm oshsa extractMin 2.8-bob.
• Bo'sh holatni tekshiring (size — 6-bo'lim).
• Kichik misolda heap holatini qo'lda chizing 0.6-bob.

"Tayyor" mezonlari (acceptance criteria)

• MinHeap insert/extract/peek heap qoidasini saqlaydi.
• MaxHeap (yoki komparator) ishlaydi.
• Priority Queue muhimlik bo'yicha chiqaradi (FIFO emas).
• Top-K eng katta/kichik K ni to'g'ri beradi.
• Heap sort to'g'ri saralaydi.
• Bo'sh/bitta/teng-priority holatlar qulamaydi.
• Har amal Big-O bilan izohlangan.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda priority-asoslangan tuzilmani — Heapni o'rgandik:

• Heap — to'liq binary tree; min-heap (ildiz eng kichik) yoki max-heap (eng katta). BST emas — faqat ota-bola munosabati.
• Massivda saqlanadi (pointer'siz): ota (i-1)/2, bola 2i+1/2i+2.
• Insert (bubble up) va extract (bubble down) — O(log n); peek — O(1).
• Priority Queue — heap ustida (eng muhim birinchi); top-K — K hajmli heap (O(n log K)); heap sort — O(n log n).
• Real: Dijkstra 3.7-bob, OS scheduler, task queue 5.22-bob.

Keyingi bob — 3.9-bob: Saralash algoritmlari (bubble, selection, insertion, merge, quick). Ma'lumotlar tuzilmalarini bildik; endi klassik saralash algoritmlarini chuqur o'rganamiz: oddiy O(n²) (bubble/selection/insertion) dan samarali O(n log n) (merge/quick) gacha — har birining ishlash mexanizmi, Big-O va qachon ishlatishi.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — heap operatsiyalari murakkabligi (insert/extract O(log n))
• Universal CS — binary heap, priority queue, heapify, top-K
• MDN Web Docs — Array (heap massivda saqlanadi — 3.2)