Priority queue va heap naqshlari: top-K, k ta ro'yxatni birlashtirish va oqim medianasi

Qisqacha: Priority queue (ustuvor navbat) — elementlar kelish tartibida emas, muhimlik tartibida chiqadigan navbat. Uni heap bilan quramiz va taqqoslovchi funksiya beramiz — shunda obyektlar ham, min va max tartib ham bitta klassda. Uchta klassik naqsh: top-K (k o'lchamli heap, O(n log k)), k ta saralangan ro'yxatni birlashtirish (O(N log k)) va oqim medianasi (ikki heap, qo'shish O(log n), mediana O(1)). JavaScript'da tayyor priority queue yo'q.

Bu darsda

• Priority queue nima ekanini va uni qanday tuzilmalar bilan qurish mumkinligini tushuntira olasiz.
• Taqqoslovchi funksiya oladigan umumiy PriorityQueue klassini yozasiz va obyektlarni bir nechta kalit bo'yicha navbatga qo'yasiz.
• Top-K va k-chi eng katta elementni k o'lchamli heap bilan topasiz.
• K ta saralangan ro'yxatni birlashtirasiz va ikki heap bilan oqim medianasini hisoblaysiz — har birini o'lchab.

Oldin bilishingiz kerak: Heap, sort va taqqoslash funksiyasi, Queue va deque (FIFO).

1. Nega bu kerak?

O'tgan darsda oshxona heap'i sonlar bilan ishladi: har buyurtma — faqat muddat. Haqiqiy buyurtma esa obyekt: taom nomi, muddat, mehmon VIP'mi, qachon kelgan. Jasur akaning qoidasi ham murakkabroq: avval VIP mehmonlar, keyin muddati yaqinlar, muddati teng bo'lsa — oldin kelgani.

Bundan tashqari, kun oxirida Jasur akada uchta yangi savol tug'ildi:

1. Million qatorli sotuvlar jurnalidan eng ko'p sotilgan 10 ta taom qaysi?
2. Beshta filial har biri o'z cheklarini vaqt bo'yicha saralab yubordi. Ularni bitta saralangan hisobotga qanday birlashtirish mumkin?
3. Cheklar kun bo'yi kelib turadi. Har yangi chekdan keyin mediana — "o'rtadagi" chek summasi qancha?

To'rtala savol bitta vosita bilan yechiladi. Bugun heap'ni universal asbobga aylantiramiz va undan uchta naqsh yasaymiz.

2. Priority queue

2.1 Navbat, lekin muhimlik bo'yicha

Priority queue (ustuvor navbat) — elementlarni qo'shish va "eng muhimini olish" amallariga ega tuzilma. Oddiy navbat "birinchi kelgan — birinchi chiqadi" qoidasida ishlaydi. Ustuvor navbatda esa eng muhim birinchi chiqadi, qachon kelganidan qat'i nazar. Kasalxonadagi tez yordam bo'limi shunday: og'ir bemor navbatsiz kiradi.

Priority queue — bu tushuncha: "qanday amallar bor" degan va'da. Uni turli tuzilmalar bilan qurish mumkin:

Heap amalda eng ko'p ishlatiladi: kodi qisqa, massivda ixcham va tez. Shuning uchun "priority queue" va "heap" ko'pincha bir xil ma'noda aytiladi. Lekin farqni biling: priority queue — nima qilinishi, heap — qanday qilinishi.

2.2 Taqqoslovchi bilan klass

O'tgan darsdagi MinHeap faqat sonlarni < bilan solishtirardi. Endi solishtirishni tashqaridan beramiz — before(a, b) funksiyasi. U a element b dan oldin chiqishi kerak bo'lsa true qaytaradi. Kod MinHeap ning o'zi, faqat a[i] < a[parent] o'rniga this.#before(a[i], a[parent]):

class PriorityQueue {
  #items = [];
  #before; // (a, b) => true, agar a b dan oldin chiqishi kerak bo'lsa

  constructor(before = (a, b) => a < b) {
    this.#before = before;
  }
  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 (!this.#before(a[i], a[parent])) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      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) return top;
    a[0] = last;
    let i = 0;
    while (true) {
      const l = 2 * i + 1;
      const r = l + 1;
      let first = i;
      if (l < a.length && this.#before(a[l], a[first])) first = l;
      if (r < a.length && this.#before(a[r], a[first])) first = r;
      if (first === i) return top;
      [a[i], a[first]] = [a[first], a[i]];
      i = first;
    }
  }
}

Sukut bo'yicha before — (a, b) => a < b, ya'ni min-heap. Max-heap uchun (a, b) => a > b beriladi. Endi «Bahor» qoidasi — uch kalitli taqqoslovchi:

let seq = 0; // kelish tartibi: teng bo'lsa — oldin kelgani
const orders = new PriorityQueue(
  (a, b) =>
    a.vip !== b.vip ? a.vip : // VIP — hammadan oldin
    a.deadline !== b.deadline ? a.deadline < b.deadline :
    a.seq < b.seq,
);
const add = (dish, deadline, vip = false) =>
  orders.push({ dish, deadline, vip, seq: seq++ });

add("osh", 30);
add("manti", 20);
add("lag'mon", 20);
add("ko'k choy", 40, true); // Dilshod aka — VIP mehmon
while (orders.size > 0) {
  const o = orders.pop();
  const mark = o.vip ? " (VIP)" : "";
  console.log(`${o.dish} — ${o.deadline} daq.${mark}`);
}

Konsolda:

ko'k choy — 40 daq. (VIP)
manti — 20 daq.
lag'mon — 20 daq.
osh — 30 daq.

Taqqoslovchini o'qiymiz. Agar ikkalasining VIP holati har xil bo'lsa — VIP bo'lgani (a.vip true bo'lsa a oldin) yutadi. Teng bo'lsa — muddat solishtiriladi. U ham teng bo'lsa — kelish raqami seq. Bu ko'p kalitli saralashdagi zanjirning o'zi, faqat || o'rniga ichma-ich shartli operator.

Ikki juftlikni qo'lda solishtirib ko'ramiz:

• "ko'k choy" (VIP) va "manti" (VIP emas): VIP holati har xil. a.vip qaytadi — ko'k choy oldin.
• "manti" (20, seq 1) va "lag'mon" (20, seq 2): ikkalasi VIP emas, muddat teng. Uchinchi kalit: 1 < 2 — manti oldin.

Heap faqat shu savolni so'raydi: "a b dan oldinmi?" Qolgan hamma ish — o'tgan darsdagi yuqoriga va pastga surish.

seq nega kerak? Heap barqaror emas: teng elementlar qaysi tartibda chiqishi kafolatlanmaydi. Sababi — pop oxirgi elementni tepaga qo'yib, pastga suradi. Shu sakrashda keyin kelgan element oldin kelganidan oldinga o'tib ketishi mumkin. "manti" va "lag'mon" ning muddati bir xil — seq siz ular istalgan tartibda chiqishi mumkin edi. Har elementga kelish raqamini qo'shish — heap'ni barqaror qilishning standart hiylasi.

Tekshirib ko'ring: Kassada eng katta chekni birinchi ko'rib chiqish kerak. new PriorityQueue(...) ga qanday taqqoslovchi berasiz? Cheklar { id, sum } obyektlari.

3. Top-K: eng kattalarning K tasi

3.1 Sodda yechim

Million sotuvdan eng ko'p sotilgan 10 ta. Birinchi fikr — saralab, boshidan 10 tasini olish:

const sales = [12, 45, 7, 30, 52, 18, 40, 25];
const top3 = sales.toSorted((a, b) => b - a).slice(0, 3);
console.log(top3); // [ 52, 45, 40 ]

Bu O(n log n): butun massiv saralanadi, holbuki bizga uning 10 ta elementi kerak. Million elementda 999 990 tasining aniq tartibi behuda hisoblanadi. Bundan tashqari, massivning nusxasi xotirada — O(n).

3.2 G'oya: eshikdagi qorovul

"Top-10" klubini tasavvur qiling. Ichkarida 10 ta joy bor, eshikda qorovul turadi. Qorovul faqat bitta narsani biladi: ichkaridagilarning eng zaifi kim. Yangi kelgan undan kuchli bo'lsa — eng zaifi chiqariladi, yangisi kiradi. Kuchsiz bo'lsa — kirmaydi.

"Ichkaridagilarning eng zaifini" bilish — min-heap'ning ishi. Diqqat: eng kattalarni qidiramiz, lekin min-heap ishlatamiz — chunki chiqarib tashlanadigani eng kichigi. Kuzating, k = 3:

Kodning asosiy uch qatori — qorovulning o'zi. Heap hali to'lmagan bo'lsa (top.size < k), yangi son shunchaki kiradi. To'lgan bo'lsa, yangi son tepadagi bilan solishtiriladi (count > top.peek()). Katta bo'lsa — tepadagi chiqariladi (pop), yangisi kiradi (push).

Har element bitta peek bilan tekshiriladi (O(1)). Kirsa — pop va push, ikkalasi O(log k). Heap hech qachon k dan oshmaydi. Jami: O(n log k) vaqt, O(k) xotira. k = 10 bo'lsa, log k ≈ 3 — amalda chiziqli.

3.3 O'lchov

Tasodifiy sonlardan eng katta 10 tasini oldik:

Heap 28–30 baravar tez. Ikkalasida ham n ikki baravar — vaqt ikki baravarga yaqin. Saralashda log n ham sezilmaydi, chunki bu oraliqda u atigi 18 dan 21 gacha o'sadi. Farq o'zgarmas ko'paytuvchida: saralash har elementni log n marta solishtiradi, heap esa ko'pchilik elementni bitta peek bilan qaytaradi — tasodifiy oqimda yangi rekordlar tobora kam uchraydi.

Xuddi shu naqsh bilan k-chi eng katta element ham topiladi. Oqim tugagach, heap tepasidagi element — k-chi eng katta. Quickselect bu savolga o'rtacha O(n) da javob beradi, lekin butun massivni xotirada talab qiladi. Heap esa ma'lumot oqim bo'lib kelganda ham ishlaydi — masalan, fayldan qatorma-qator o'qilganda.

Tekshirib ko'ring: Eng arzon 5 ta taomni topish kerak. Qanday heap ishlatiladi va qaysi shartda yangi element kiradi?

4. K ta saralangan ro'yxatni birlashtirish

4.1 G'oya

Beshta filial cheklarni vaqt bo'yicha saralab yubordi. Bitta saralangan hisobot kerak. Sodda yo'l — hammasini bitta massivga qo'shib, saralash: O(N log N), N — jami cheklar soni.

Lekin har ro'yxat allaqachon saralangan. Har ro'yxatning eng kichigi — uning birinchi elementi. Demak, umumiy eng kichigi — k ta "birinchi"lardan biri. Ularni heap'ga qo'yamiz. Eng kichigini olamiz, natijaga yozamiz va o'sha ro'yxatning keyingi elementini heap'ga qo'yamiz. Heap'da doim k tadan ko'p element bo'lmaydi.

Hayotiy rasm: to'rtta filialning kassiri har biri o'z cheklar dastasini vaqt bo'yicha taxlab qo'ygan. Jasur aka faqat dastalarning eng ustki cheklariga qaraydi. Eng ertasini oladi, hisobotga yozadi — o'sha dastada keyingi chek ochiladi. Qolgan dastalarning ichini varaqlashning hojati yo'q.

Bu yerda ikkita o'lcham bor: k — ro'yxatlar (filiallar) soni, N — hamma ro'yxatlardagi jami elementlar. Kuzating, k = 4 (bittasi bo'sh), N = 7:

function mergeSorted(lists) {
  // [qiymat, ro'yxat raqami, ro'yxatdagi o'rni]
  const heap = new PriorityQueue((a, b) => a[0] < b[0]);
  lists.forEach((list, i) => {
    if (list.length > 0) heap.push([list[0], i, 0]);
  });
  const result = [];
  while (heap.size > 0) {
    const [value, i, j] = heap.pop();
    result.push(value);
    if (j + 1 < lists[i].length) {
      heap.push([lists[i][j + 1], i, j + 1]); // keyingisi
    }
  }
  return result;
}

// filiallarning cheklari vaqti (soat 9:00 dan daqiqa)
const branches = [[5, 40, 90], [12, 13], [], [1, 60]];
console.log(mergeSorted(branches).join(" "));

Konsolda:

1 5 12 13 40 60 90

Heap'dagi har element — uchta sondan iborat massiv: qiymat, qaysi ro'yxatdan va ro'yxatning qaysi o'rnidan. Taqqoslovchi faqat birinchisiga qaraydi. Qolgan ikkitasi "keyingi chekni qayerdan olaman?" degan savolga javob beradi: lists[i][j + 1]. Bo'sh ro'yxat (uchinchi filial) boshida o'tkazib yuboriladi.

Vaqt: N ta element, har biri bir marta heap'ga kiradi va chiqadi. Heap'da ko'pi bilan k ta element bor, shuning uchun har kirish-chiqish O(log k). Jami — O(N log k). k = 5 bo'lsa, log k ≈ 2: har element atigi ikki-uch qavat yuradi.

4.2 Halol o'lchov

100 ta ro'yxat, jami N son. flat() + sort bilan solishtirdik:

Deyarli teng! Sababi — V8 dagi TimSort (JS sort ichidan): u massivdagi tayyor saralangan bo'laklarni ("run") topadi va ularni birlashtiradi. Ya'ni sort ichida xuddi shu g'oya ishlaydi.

Unda heap qachon kerak? Ro'yxatlar xotiraga sig'maganda. Har filialning yillik hisoboti — gigabaytlik fayl. flat() hammasini bitta massivga yig'ishi kerak — xotira yetmaydi. Heap usuli esa har fayldan faqat bittadan joriy qatorni ushlaydi (O(k) xotira) va natijani ham oqim bilan yozadi.

Bu usulning nomi bor: tashqi saralash (external sort) — xotiraga sig'maydigan ma'lumotni bo'laklab saralash. Avval har bo'lak alohida saralanib, diskka yoziladi. Keyin saralangan bo'laklar aynan shu heap bilan birlashtiriladi. Ma'lumotlar bazalari katta jadvalni saralaganda shunday qiladi.

5. Oqim medianasi: ikki heap

5.1 Masala

Mediana — saralangan ro'yxatning o'rtasidagi qiymat. Juft sonli bo'lsa — o'rtadagi ikkitasining o'rtachasi. U o'rtacha arifmetikdan farqli: bitta juda katta chek (to'y buyurtmasi) uni deyarli o'zgartirmaydi. Shuning uchun "tipik chek qancha?" savoliga mediana yaxshiroq javob beradi.

Cheklar kun bo'yi keladi va har chekdan keyin mediana kerak. Sodda yechim — cheklarni saralangan massivda saqlash: o'rni ikkiga bo'lib topiladi, splice bilan qo'yiladi, mediana — o'rtadagi element. Har qo'shish O(n), jami O(n²).

5.2 G'oya

Medianaga kerak bo'lgan narsa — faqat o'rtadagi bir-ikki element. Cheklarni ikki yarmiga bo'lamiz:

• pastki yarim — kichiklari; bizga ularning eng kattasi kerak → max-heap;
• yuqori yarim — kattalari; bizga ularning eng kichigi kerak → min-heap.

Ikki qoida: pastki yarimning hamma elementi yuqoridagilardan kichik yoki teng; yarimlar o'lchami teng yoki pastkisi bittaga ko'p. Shunda mediana — yo pastki tepasi, yo ikki tepaning o'rtachasi. Kuzating:

Kodni o'qiymiz. add uch ish qiladi:

1. Qayerga? Yangi chek pastki yarimning eng kattasidan kichik yoki teng bo'lsa — pastga (lower), aks holda yuqoriga (upper). Shunda birinchi qoida saqlanadi: pastdagilar yuqoridagilardan katta emas.
2. Muvozanat. Pastki yarim ikkitaga ko'payib ketsa, uning eng kattasi yuqoriga o'tadi. Yuqorisi ko'payib ketsa, uning eng kichigi pastga o'tadi. Chegaradagi element o'tgani uchun birinchi qoida buzilmaydi.
3. median faqat tepalarga qaraydi. Cheklar soni toq bo'lsa, pastki yarim bittaga ko'p — mediana uning tepasi. Juft bo'lsa — ikki tepaning o'rtachasi.

Har qo'shish — bitta-uchta heap amali, O(log n). Mediana — ikki tepaga qarash, O(1).

Tekshirib ko'ring: 40, 10 va 30 dan keyin kassaga 5 ming so'mlik chek keldi. U qaysi yarimga tushadi, muvozanatdan keyin yarimlarda nima qoladi va mediana qancha bo'ladi?

5.3 O'lchov

Har yangi chekdan keyin medianani hisobladik:

Ikki heap: n ikki baravar — vaqt ×2,0–2,2 (n log n). Saralangan massiv: ×3,3–4,2 (n²). 200 000 chekda farq 40 baravar.

6. JavaScript'da heap yo'q

Python'da heapq, Java'da PriorityQueue, C++ da std::priority_queue bor. JavaScript standartida esa — yo'q. Uch yo'l:

1. O'zingiz yozasiz — shu darsdagi 45 qatorlik klass. Intervyularda aynan shu kutiladi. Yozib, yod olib qo'ying.
2. Tayyor paket — masalan, npm'dagi @datastructures-js/priority-queue (6.4.0 versiya, 2026-iyul). npm paketlarini 16-qismda o'rganamiz, hozir bilish shart emas.
3. Kichik hajmda — massiv. O'nlab element bo'lsa, har safar toSorted yoki Math.min bilan qidirish ham mikrosoniyalar. Heap'ni o'lchov kerak deganda qo'shing.

7. Chegaraviy holatlar

• Bo'sh navbat. pop va peek — undefined. Top-K'da elementlar k tadan kam bo'lsa — heap'da borlari qaytadi, bu ham to'g'ri javob.
• k = 0. Top-K bo'sh ro'yxat. kthLargest(…, 0) ma'nosiz — tekshirib, xato qaytaring.
• Teng ustuvorlik. Heap barqaror emas — kerak bo'lsa seq qo'shing.
• Bo'sh ro'yxatlar. Birlashtirishda boshida o'tkazib yuboriladi; hamma ro'yxat bo'sh bo'lsa — bo'sh natija.
• Mediana bo'sh oqimda. lower.peek() — undefined, natija NaN. Hech bo'lmasa bitta chek kelguncha medianani so'ramang.

8. Ko'p uchraydigan xatolar

8.1 sort uslubidagi taqqoslovchi

sort taqqoslovchisi son qaytaradi (a - b), bizning before esa mantiqiy qiymat. Ularni aralashtirish xato xabarisiz noto'g'ri tartib beradi:

// ❌ sort uslubidagi taqqoslovchi: son qaytaradi
const wrong = new PriorityQueue((a, b) => a - b);
for (const v of [30, 10, 20]) wrong.push(v);
console.log(wrong.pop(), wrong.pop(), wrong.pop()); // 20 30 10

a - b faqat a = b bo'lganda 0 (yolg'on), qolgan hamma holatda — true ga teng bo'lgan son. Heap "har doim almashtir" deb tushunadi. Tuzatish: (a, b) => a < b yoki klassingiz qaysi shaklni kutishini aniq hujjatlang.

8.2 Top-K uchun noto'g'ri heap

Eng kattalar uchun max-heap olib, oxirida k marta pop qilish — butun ma'lumotni heap'ga solish degani: O(n) xotira va O(n + k log n) vaqt. Tuzatish: k o'lchamli min-heap — qorovul eng zaifini biladi.

8.3 Medianada yarimlarni muvozanatlamaslik

Faqat "kichik bo'lsa pastga, katta bo'lsa yuqoriga" qilib, o'lchamlarni tenglashtirmasa — tepalar o'rtani ko'rsatmaydi. Tuzatish: har qo'shishdan keyin o'lchamlarni tekshiring.

8.4 Heap'ni massiv kabi aylanish

for (const x of heap.items) — elementlar ustuvorlik tartibida emas. Tuzatish: tartib kerak bo'lsa — pop bilan oling.

9. Mashqlar

1-mashq (oson): Naqshni tanlang

Har vaziyat uchun naqshni va heap turini ayting:

• (a) 1 000 000 mehmon orasidan eng ko'p tashrif buyurgan 20 tasi;
• (b) 30 kunlik saralangan hisobotlarni bitta oylik hisobotga birlashtirish;
• (c) har yangi baho kelganda reytingning medianasi;
• (d) navbatdagi eng yaqin bron vaqti.

2-mashq (o'rta): Eng ko'p sotilgan taomlar

Sotuvlar jurnali — taom nomlari ro'yxati (["osh", "manti", "osh", …]). topDishes(log, k) funksiyasini yozing: eng ko'p sotilgan k ta taom va sonini qaytarsin. Ishora: avval Map bilan sanang (Hash map bilan hisoblash naqshlari), keyin [nom, son] juftlariga top-K naqshini qo'llang.

function topDishes(log, k) {
  const counts = new Map();
  for (const dish of log) {
    counts.set(dish, (counts.get(dish) ?? 0) + 1);
  }
  // [nom, son] juftlari, son bo'yicha min-heap
  const top = new PriorityQueue((a, b) => a[1] < b[1]);
  for (const entry of counts) {
    top.push(entry);
    if (top.size > k) top.pop(); // eng kam sotilgani chiqadi
  }
  const result = [];
  while (top.size > 0) result.push(top.pop());
  return result.reverse();
}

const log = ["osh", "manti", "osh", "ko'k choy", "osh", "manti",
  "lag'mon"];
console.log(topDishes(log, 2)); // [ [ 'osh', 3 ], [ 'manti', 2 ] ]

3-mashq (qiyin): Naqshlar testlari

kurs/mashqlar/14/43-pq/pq.test.mjs faylida darsdagi PriorityQueue, mergeSorted va kthLargest(values, k) ni (k o'lchamli min-heap bilan) yozing. Testlar (node:test): obyektlar teng muddatda kelish tartibida chiqadi; bo'sh ro'yxatlar bilan birlashtirish va bo'sh kirish; k-chi eng katta — takrorlar bilan.

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

class PriorityQueue {
  #items = [];
  #before; // (a, b) => true, agar a b dan oldin chiqishi kerak bo'lsa

  constructor(before = (a, b) => a < b) {
    this.#before = before;
  }
  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 (!this.#before(a[i], a[parent])) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      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) return top;
    a[0] = last;
    let i = 0;
    while (true) {
      const l = 2 * i + 1;
      const r = l + 1;
      let first = i;
      if (l < a.length && this.#before(a[l], a[first])) first = l;
      if (r < a.length && this.#before(a[r], a[first])) first = r;
      if (first === i) return top;
      [a[i], a[first]] = [a[first], a[i]];
      i = first;
    }
  }
}

function mergeSorted(lists) {
  // [qiymat, ro'yxat raqami, ro'yxatdagi o'rni]
  const heap = new PriorityQueue((a, b) => a[0] < b[0]);
  lists.forEach((list, i) => {
    if (list.length > 0) heap.push([list[0], i, 0]);
  });
  const result = [];
  while (heap.size > 0) {
    const [value, i, j] = heap.pop();
    result.push(value);
    if (j + 1 < lists[i].length) {
      heap.push([lists[i][j + 1], i, j + 1]); // keyingisi
    }
  }
  return result;
}

function kthLargest(values, k) {
  const top = new PriorityQueue(); // k o'lchamli min-heap
  for (const v of values) {
    top.push(v);
    if (top.size > k) top.pop();
  }
  return top.peek();
}

test("obyektlar: teng muddatda — kelish tartibi", () => {
  let seq = 0;
  const q = new PriorityQueue((a, b) =>
    a.deadline !== b.deadline
      ? a.deadline < b.deadline
      : a.seq < b.seq);
  for (const dish of ["osh", "manti", "lag'mon"]) {
    q.push({ dish, deadline: 20, seq: seq++ });
  }
  q.push({ dish: "ko'k choy", deadline: 5, seq: seq++ });
  const order = [];
  while (q.size > 0) order.push(q.pop().dish);
  assert.deepEqual(order, ["ko'k choy", "osh", "manti", "lag'mon"]);
});

test("k ta saralangan ro'yxat — bitta", () => {
  const branches = [[9, 14, 20], [8, 11], [], [10, 12, 21]];
  const all = [8, 9, 10, 11, 12, 14, 20, 21];
  assert.deepEqual(mergeSorted(branches), all);
  assert.deepEqual(mergeSorted([]), []);
});

test("k-chi eng katta", () => {
  const checks = [120, 45, 300, 45, 80, 210];
  assert.equal(kthLargest(checks, 1), 300);
  assert.equal(kthLargest(checks, 3), 120);
  assert.equal(kthLargest(checks, 6), 45);
});

✔ obyektlar: teng muddatda — kelish tartibi (1.3482ms)
✔ k ta saralangan ro'yxat — bitta (0.2669ms)
✔ k-chi eng katta (0.231ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 75.9485

4-mashq: Amaliy tajriba — naqshlar qatorlari

kurs/mashqlar/14/MURAKKABLIK.md ga uchta naqshni qo'shing, har biriga sodda yechim bilan solishtirish va o'lchov ustuni.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Top-K | toSorted + slice | O(n log n) | O(n) |
| Top-K | k o'lchamli min-heap | O(n log k) | O(k) |
| K ta ro'yxatni birlashtirish | flat + sort | O(N log N) | O(N) |
| K ta ro'yxatni birlashtirish | k elementli heap | O(N log k) | O(k) + natija |
| Oqim medianasi | saralangan massiv | O(n) har qo'shish | O(n) |
| Oqim medianasi | ikki heap | O(log n) / O(1) | O(n) |

git add 14/MURAKKABLIK.md 14/43-pq
git commit -m "14/43: top-K, ro'yxatlarni birlashtirish, mediana"

10. Real ishda

• Vazifalar navbatlari. Backend'dagi fon vazifalari (email yuborish, hisobot yasash) ustuvorlik bilan bajariladi — navbat tizimlari ichida priority queue bor. Ma'lumotlar bazasi asosidagi navbatni 26-qismda ko'ramiz.
• Monitoring. "Eng sekin 10 ta so'rov", "eng ko'p xato bergan 5 ta endpoint" — top-K, ko'pincha oqim ustida.
• Statistika. Javob vaqtining medianasi (va p95, p99) — kuzatuv tizimlarida asosiy ko'rsatkich. Katta oqimlarda taxminiy usullar ham ishlatiladi, lekin g'oya — "o'rtani tez bilish".
• Graflar. Dijkstra — priority queue bilan eng qisqa yo'l. U yerda xuddi shu g'oyadagi heap [vaqt, tugun] juftlarini vaqt bo'yicha tartiblaydi.
• Intervyu. "Kth Largest Element", "Top K Frequent Elements", "Merge k Sorted Lists", "Find Median from Data Stream" (LeetCode 215, 347, 23, 295) — eng mashhur heap savollari.

Xulosa

• Priority queue — muhimlik bo'yicha chiqadigan navbat; heap — uning eng ko'p ishlatiladigan qurilishi.
• Taqqoslovchi before(a, b) bitta klassni min, max va obyektlar uchun ishlatadi; teng ustuvorlikda tartib uchun seq qo'shing.
• Top-K: k o'lchamli min-heap — O(n log k), O(k) xotira. 2 mln sonda top-10 — 22 ms, saralash bilan — 639 ms.
• K ta saralangan ro'yxat — heap'da har ro'yxatdan bittadan, O(N log k); xotirada sort deyarli teng, lekin oqim va fayllarda heap yutadi.
• Oqim medianasi — ikki heap: qo'shish O(log n), mediana O(1); 200 000 chekda saralangan massivdan 40 baravar tez.

Keyingi dars: Segment tree va Fenwick tree — o'zgarib turadigan massivda "l dan r gacha yig'indi" so'rovlarini O(log n) da bajarish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 6-bob (heapsort va priority queues).
• LeetCode 215, 347, 23, 295 — leetcode.com (shartlari boshqacha, g'oyasi shu darsdagi).
• npm: @datastructures-js/priority-queue — npmjs.com (6.4.0, 2026-07-30 holatiga)
• Python hujjatlari: heapq — docs.python.org (boshqa tillardagi tayyor heap bilan solishtirish uchun)