Binar qidiruv algoritmi. Binar qidiruv daraxti. Prioritetli navbat. Binar qidiruv algoritmi

Prioritetli navbat

• Sonlar navbatini saqlash uchun tuzilma. Navbat boshida hamisha pririteti katta element turadi.
• Ikkita amal bajariladi:
• 1. Yangi element qo’shish
• 2. Prioriteti eng katta bo’lgan elementni o’chirish

Prioritet sifatida sonning o’zining qiymatini yoki alohida yangi qiymat ishlatimiz mumkin. Qiymati eng kichigi prioriteti eng katta qilib olish ham mumkin.

Nomlanishi

• Ruschada – Куча yoki пирамида, inglizchada – heap,
• O’zbekchada uyum, to’da degan ma’noni beradi.

Tuzilmasi

• To’liq ikkilik daraxt ko’rinishiga ega bo’ladi. Har bir uzeldagi qiymat uning farzandlari qiymatlaridan katta bo’ladi.
• Massiv shaklida saqlanadi. i-uch uchun:
• 2i va 2i+1 uchlar farzandlar.
• i/2 uch otasi

heap[i]<=heap [2i] va

heap [i]<=heap [2i+1]

Elementlar 1 dan nomerlanadi.

Daraxtning balandligi log(n).

Misol

Element qo’shish

• Elementni massiv ohiriga qo’shamiz;
• Qo’shilgach heap qoidasi buzilishi mumkin.

Element qo’shish(2)

• Agar heap qoidasi buzulsa uni qayta tiklash lozim. Buning uchun yoqoriga toki qaralayotgan uch qiymati o’zining otasi qiymatidan kichik yoki teng bo’lgunga qadar davom ettiramiz.

void add(int x) {

• void add(int x) {
• size++;
• heap[size] = x;
• int i = size;
• while (i > 1) {
• if (heap[i / 2] > heap[i]) {
• int t = heap[i];
• heap[i] = heap[i / 2];
• heap[i / 2] = t;
• i = i / 2;
• } else {
• break;
• }
• }
• }

Minimalni o’chirish

• Minimal qiymat hamisha massivning birinchi uchida joylashadi(heap[1]).
• Uning o’rniga massivning oxirgi elementini joylashtiramiz. Natijada heap ning asosiy hossasi buzilishi mumkin. Uni tiklash uchun pasga tamon toki qoida tiklangunga qadar harakatlanamiz.