Kompyuter injinering fakulteti

Qo‘shnilik(qo‘shni tugunlar) ro‘yxati – bu A[n] massiv bo‘lib, A[i] xar bir elementi i tugun bilan qo‘shni tugunlar ro‘yxatini o‘zida saqlaydi.
Qo‘shnilik(qo‘shni tugunlar) ro‘yxati qulaylik tomonlari quyidagilarda:

• 
  Joriy (berilgan) tugunga qo‘shni tugunni izlash;
  
• 
  Tugun yoki qirra(yoy)larni qushish;
  
• 
  Siyrak graflar bilan ishlash.
  

Qo‘shnilik(qo‘shni tugunlar) ro‘yxati noqulayliklari esa quyidagicha:

• 
  Qirra(yoy)ning mavjudligini tekshirish;
  
• 
  Tugun yoki qirra(yoy)larni o‘chirish.
  

Qirralar ro‘yxati – qirralarning qo‘shni tugunlar juftliklaridan iborat chiziqli ro‘yxatdir.
Qo‘shnilik(qo‘shni tugunlar) ro‘yxati qulaylik tomonlari quyidagilarda:

• 
  Qirra(yoy)larni qushish yoki o‘chirish;
  
• 
  Yoylarning yuklanishi bo‘yicha tartiblash;
  
• 
  Siyrak graflar bilan ishlash.
  

Qo‘shnilik(qo‘shni tugunlar) ro‘yxati noqulayliklari esa quyidagicha:
Tugun va qirra(yoy)ning qo‘shniligini aniqlash;

• 
  Berilgan tugunga intsidient qirra(yoy)larni tanlash.
  
• 
  Chuqurlikka qarab ko‘rishda stek tuzilmasi qo‘llaniladi.
  
• 
  Kenglikka qarab ko‘rishda esa navbat tuzilmasidan foydalaniladi.
  

14) Complete binary tree nima ekanligi haqida bu yerda tushuntirib o‘tilgani uchun, maxsus tartiblangan ma’nosiga to‘xtalamiz.
Binary heap bo‘lishi uchun tree’da ma’lumotlar shajara bo‘yicha o‘sish tartibida (max heap) yoki kamayish tartibida (min heap) joylashgan bo‘lishi kerak
Complete binary tree nima ekanligi haqida bu yerda tushuntirib o‘tilgani uchun, maxsus tartiblangan ma’nosiga to‘xtalamiz.
Binary heap bo‘lishi uchun tree’da ma’lumotlar shajara bo‘yicha o‘sish tartibida (max heap) yoki kamayish tartibida (min heap) joylashgan bo‘lishi kerak.

Binary heap nima uchun kerak?

Qisqa javob – heap’dagi eng katta (yoki eng kichik) elementni topish uchun kerak. Bunda binary heap tuzilishi tree bo‘lgani uchun eng pastki elementdan eng yuqori elementga chiqish uchun O (log N) urinish lozim. Masalan yuqoridagi rasmda har bir tree’da 7 ta node bo‘lsa, pastdan yuqoriga chiqish – log₂7 = 2.8 ~ 2 ta urinishda bo‘ladi.
Priority queue maqolasida biz ro‘yhatdan eng katta va eng kichik elementni topishni ko‘rgan edik. Uning kamchiligi – tartiblanmagan array uchun eng katta (yoki eng kichik) elementni topishda time complexity O(N) bo‘lib ketayotgan edi. Tartiblangan array uchun esa, eng katta (eng kichik) elementni topish O(1) bo‘ladi, lekin bunda array element qo‘shganimizda har safar array’ni tartiblashga majbur bo‘linardi – O(N log N).
Demak, Binary heap Priority queue’dan ko‘ra samaraliroq ishlaydi. Qo‘shish va o‘chirish – binary tree’dagi kabi O (log N).
Binary heap’ning kamchiligi – u faqat eng katta (eng kichkina) elementlarni tezda topish imkonini beradi. Boshqa qiymatdagi elementlarni topish uchun heapni «titkilab» chiqish kerak. Sababi binary heap – tartiblanmagan. Tabiiyki tartiblanmagan ro‘yhatdan qidirish O(N) vaqtni oladi. Masalan yuqoridagi rasm’dan 30 sonini topish uchun heap’ning hamma elementlari tekshirib chiqish kerak bo‘ladi.

Kodda ifodalash

Binary heap uchun double pointer’li linked list ishlatish shartmas. Shunchaki array bilan ham ifodalasa bo‘ladi.
Amallar osonroq bo‘lishi uchun array[0] ni bo‘sh qoldiramiz, keyin heap qiymatlarini kiritamiz. Bizda Max heap’ni kodda ifodalash
const array = [null, 100, 70, 80, 20, 30, 20, 50]
Min heap:
const array = [null, 10, 14, 17, 20, 30, 21, 44]
Agar biz array’dan i-nchi elementni ko‘rsak:

• 
  uning parent’i – floor (i-1)/2 indeksda;
  
• 
  uning chap child’i – 2 * i indeksda;
  
• 
  uning o‘ng child’i – 2 *i + 1 indeksda.
  

15) Kompyuterda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri 
hisoblanadi. Uning vazifasi berilgan argument bo‘yicha massiv ma’lumotlari 
ichidan mazkur argumentga mos ma’lumotlarni topish yoki bunday ma’lumot 
yo‘qligini aniqlashdan iborat. Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl
deb ataladi. Ixtiyoriy ma’lumot (yoki tuzilma elementi) boshqa ma’lumotdan 
biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob 
bo‘lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagona bo‘lishi mumkin.
Bunday noyob kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir 
jadvalda takrorlansada u orqali ham qidiruvni amalga oshirish mumkin.
Ma’lumotlar kalitini bir joyga yig’ish (boshqa jadvalga) yoki yozuv sifatida
ifodalab bitta maydonga kalitlarni yozish mumkin. Agar kalitlar ma’lumotlar
jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar 

tashqi kalitlar deyiladi. Aks holda, ya’ni yozuvning bir maydoni sifatida jadvalda 

saqlansa ichki kalit deyiladi. Kalitni berilgan argument bilan mosligini
aniqlovchi algoritmga berilgan argument bo‘yicha qidiruv deb ataladi. Qidiruv
algoritmi vazifasi kerakli ma’lumotni jadvaldan topish yoki yo‘qligini
aniqlashdan iboratdir. Agar kerakli ma’lumot yo‘q bo‘lsa, u holda ikkita ishni 
amalga oshirish mumkin:
1. Ma’lumot yo‘qligini indikatsiya qilish (belgilash)
2. Jadvalga ma’lumotni qo‘yish.
Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) – ma’lumot
mavjud. Key – qidiruv argumenti. Unga rec - informatsion yozuv mos qo‘yiladi.
Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvning bir  necha turlari
mavjud.