Texnologiyalari universiteti Farg’ona filiali 730-20 guruh talabasi Mamajonov Raximberdining Ma'lumotlar tuzilmasi va

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.
  

12. 
    

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’lumotda n

biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noy ob

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 jadvald a

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.