Algoritmdan nazorat savollariga javoblar Algoritm nima

27. 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.
  

• 
  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) {
  
• 
  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;
  
• 
  }
  
• 
  }
  
• 
  }