Mavzu: Ustivor navbatlar. Reja 1: Ustuvor navbat. 2: Maksimal elementni izlash Ustuvor navbat - bu yozuvlar bir-biri bilan chiziqli taqqoslanadigan kalitlarga (masalan, raqamlar) ega bo'lgan va ikkita amalni realizatsiya qiladigan axborot tizimidir. Bu ikki aml tizimga tasodifiy yozuvni kiritish va yozuv tizimidan eng kichigi bilan tanlov kalit. Dasturiy ta'minot tizimlarida ustuvor navbatlar juda keng tarqalgan va dasturlarning ishlashi to'g'ridan-to'g'ri ularni amalga oshirish samaradorligiga bog'liq. Ushbu ma'ruzada biz eng soddalikdan boshlab ustuvor navbatni amalga oshirishning bir necha usullarini ko'rib chiqamiz. Qo’llab-quvvatlanadigan amallar: 1) Insert - navbatga element qo'shish 2)Max - ustuvorligi yuqori bo'lgan elementni qaytaradi 3)ExtractMax - navbatdagi eng ustuvor elementni olib tashlaydi 4)IncreaseKey - berilgan elementning ustuvor qiymatini o'zgartiradi 5)Merge - ikkita navbatni bittaga birlashtiradi Binar uyum (kucha) - piramida (binary heap) Binar uyum (uyum, saralash daraxti, binary heap) bu quyidagi shartlarni qanoatlantiradigan binar daraxtdir: Har qanday uchning ustuvorligi, uning avlodlarining ustuvorligidan kichik emas. Daraxt to'liq ikkilik daraxt bo’lishi uchun (complete binary tree) - barcha darajalar chapdan o'ngga to'ldiriladi (oxirgisi bundan mustasno bo’lishi mumkin). Tabiatdagi to’liq binar daraxti Ustivor navbatlar haqida qo'shimcha jihatlar va misollar keltirish mumkin: Moslashuvchanlik: Ustivor navbatlar turli vaziyatlarga moslasha oladi. Masalan, muayyan vaqtlarda ko'proq mijozlar kelganda, navbatlarni kengaytirish yoki qo'shimcha xodimlarni jalb qilish mumkin. Ish jarayonini optimallashtirish: Ustivor navbatlar yordamida ish jarayonini optimallashtirish mumkin. Agar biror vazifa ko'p vaqt talab qilsa, xodimlar navbatlar orqali ushbu vazifalarni bir-biriga taqsimlab, tezroq bajarishlari mumkin. Tezkor feedback: Navbatlar orqali mijozlar yoki xodimlardan tezkor fikr olish mumkin. Ular o'z tajribalarini baham ko'rish orqali xizmat sifatini yaxshilashga yordam beradi. O'qitish va o'sish: Yangi xodimlar ustivor navbatlar orqali tajriba orttirishlari va jamoa ichida o'z o'rnini topishlari uchun yaxshi imkoniyat yaratadi.Misol sifatida, restoranlarda yoki banklarda ustivor navbatlar tizimi ko'p ishlatiladi. Misol uchun, bankda mijozlar navbatda kutib, o'z ishlarini bajarishadi. Bu jarayonni optimallashtirish va samaradorligini oshirish uchun maxsus navbat tizimlari, masalan, raqamli navbatlar yoki mobil ilovalar ham qo'llaniladi. Texnologiyalardan foydalanish: Hozirgi kunda ustivor navbatlar tizimini rivojlantirish uchun turli texnologiyalar, masalan, mobil ilovalar, raqamli navbat boshqaruv tizimlari va onlayn xizmatlar qo'llaniladi. Bu jarayonni yanada osonlashtiradi va mijozlarga qulayliklar yaratadi. Muammolarni hal qilish: Ustivor navbatlar yordamida xodimlar muammolarni tezda hal qilish imkoniyatiga ega bo'lishadi. Agar biron bir vazifa yoki xizmat ko'rsatish jarayonida muammo yuzaga kelsa, bu jarayonni boshqarish osonlashadi. O'qitish imkoniyatlari: Ustivor navbatlar orqali yangi xodimlarga o'qitish va ularni ish jarayoni bilan tanishtirish uchun samarali platforma bo'lib xizmat qiladi. Bu, ayniqsa, murakkab xizmat ko'rsatish sohalarida juda foydali. Stressni kamaytirish: Tartibga solingan navbatlar xodimlarning stress darajasini kamaytirishi mumkin. O'z vazifalarini aniq bilish va tartibda ishlash, ish joyidagi muammolarni kamaytirishga yordam beradi. Misollar: Supermarketlar: Mijozlar kassa oldida navbatda turishadi, bu esa har bir kishi o'z navbatini kutishiga imkon beradi va xarid jarayonini tartibga soladi. Sog'liqni saqlash muassasalari: Poliklinikalarda yoki shifoxonalarda bemorlar o'z navbatida qabul qilinadi, bu esa jarayonni samarali tashkil etadi. 2: Maksimal elementni izlash Binar kuchaga element joylashtirish Heapsort (Heapsort, "Heap sorting") - n elementlarni saralashda O(nlogn) amallarda eng yomon, o'rtacha va eng yaxshi (ya'ni kafolatlangan) holda ishlaydigan saralash algoritmi. Ishlatiladigan qo'shimcha xotira miqdori massiv kattaligiga bog'liq emas. Ushbu saralashni pufaksimon saralashning rivojlantirilgan ko’rinishi deb qarash mumkin. Eng yomon vaqt - O(nlog(n) Eng yaxshi vaqt - O(nlog(n) O’rtacha vaqt - O(nlog(n) Heap-Sort algoritmini realizatsiya qilish #include <iostream> #include <time.h> using namespace std; int main() { srand(time(NULL)); int const n = 100; int a[n]; for ( int i = 0; i < n; ++i ) { a[i] = rand()%1000; cout << a[i] << " "; } //massivni to'ldirish //-----------Saralash------------// //O'sish bo'yicha saralash. int sh = 0; //смещение bool b = false; for(;;) //Sikl cheksiz davom etadi { b = false; for ( int i = 0; i < n; i++ ) { if( i * 2 + 2 + sh < n ) { if( ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 + sh] ) ) { if ( a[i * 2 + 1 + sh] < a[i * 2 + 2 + sh] ) { swap( a[i + sh], a[i * 2 + 1 + sh] ); b = true; } else if ( a[i * 2 + 2 + sh] < a[ i * 2 + 1 + sh]) { swap( a[ i + sh], a[i * 2 + 2 + sh]); b = true; } } // oxirgi ikki element uchun qo'shimcha tekshirish // ushbu tekshiruv yordamida siz piramidani saralashingiz mumkin // faqat uchta elementdan iborat if( a[i*2 + 2 + sh] < /*>*/ a[i*2 + 1 + sh] ) { swap( a[i*2+1+sh], a[i * 2 +2+ sh] ); b = true; } } else if( i * 2 + 1 + sh < n ) { if( a[i + sh] > /*<*/ a[ i * 2 + 1 + sh] ) { swap( a[i + sh], a[i * 2 + 1 + sh] ); b = true; } } } if (!b) sh++; if ( sh + 2 == n ) break; } //Saralash tugatildi //Natijani chiqarish cout << endl << endl; for ( int i = 0; i < n; ++i ) cout << a[i] << " "; // getch(); return 0; }