|
Referat bajardi: 739-22 guruh talabasi Axmedov Izzatilla Qabul qildi: farg’ona-2024
|
| bet | 3/7 | | Sana | 13.06.2024 | | Hajmi | 208,96 Kb. | | #263487 | | Turi | Referat |
Bog'liq 1. Stack. queue.priority queue.BST orqali amalga oshirish
Ikkilik qidiruv daraxti yordamida ustuvor navbatning funksionalligini ham amalga oshirishimiz mumkin. Oddiy BST qo’shish va o’chirish uchun O(logn) ni oladi. Biz, shuningdek, eng yomon holatda ham o (logn) murakkabligini qo’llab-quvvatlash uchun AVL Tree, Red-Black Tree va boshqalar kabi o’z-o’zini muvozanatlashtiruvchi BST dan foydalanishimiz mumkin.
Eng ustuvor elementni ertica vaqti doimiy vaqtda amalga oshirilishi mumkin. Biz eng yuqori ustuvor elementni saqlash uchun qo’shimcha ko’rsatgichni saqlashimiz mumkin va uni kiritish va o’chirish amalga oshirilganda yangilanishi mumkin. O’chirish operatsiyasi bilan biz tartib o’rnini topib, qo’shimcha ko’rsatgichni yangilaymiz.
Heaps orqali amalga oshirish
Odatda ustunlik navbatini amalga oshirish uchun to’plar afzallik beriladi. Uyumlarda enqueue() va dequeue() O(log n) vaqtida bajarilishi mumkin.
Eng ustuvor element ildiz tugunida mavjud bo’ladi. Uyum asosiy ustuvor element doimiy vaqtda topilishi uchun asosiy tugunda bo’ladigan xususiyatga tuzilishi mumkin.
BST va to’plamlar ustuvor navbat operatsiyalarini bajarish uchun bir xil vaqt murakkabligini oladi, lekin ustunlik navbati amalga oshirilganda to’plarga afzallik beriladi. Bunga quyidagi sabablar sabab bo'ladi:
Uyumlar massivlar yordamida amalga oshiriladi, shuning uchun u ko'rsatkichlar uchun qo'shimcha joy talab qilmaydi. Ota-bola munosabatlari indekslar bo'yicha to'plamlarda saqlanadi.
Uymalarni O(N) vaqtida qurish mumkin, lekin Oʻz-oʻzini muvozanatlash BST qurish uchun O(nLogn) vaqtni talab qiladi.
Amaliyotlar bir xil vaqtda murakkab, lekin Ikkilik qidiruv daraxtidagi konstantalar yuqoriroq.
Fibonachchi Heap kabi Binary Heapning o'zgarishlari mavjud bo'lib, ular D(1) vaqtida kiritish va kamaytirish tugmachalarini qo'llab-quvvatlaydi.
Navbatdagi operatsiya
Elementni ustuvor navbatga qo'shish (maksimal yig'ish) quyidagicha amalga oshiriladi
Yangi elementni daraxtning oxiriga qo’ying.
Daraxtni yig’ish, ya’ni yangi daraxtni uyumga aylantirish.
|
| |
