uyum (kucha) - saralash (binary heap)

DOC 18 sahifa 94,5 KB Bepul yuklash

18 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 94,5 KB

Fayl turi DOC

Sahifalar 18

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 18

uyum (kucha) - saralash (binary heap). reja 1 uyum (kucha) - piramida (binary heap). 2 asimptotik optimallik. 3 uyma tartiblash. 4 uyumni saralash algoritmi. ko'pgina ilovalar kalitlarga ega bo'lgan elementlarni qayta ishlashni talab qiladi, lekin ular to'liq tartibda va birdaniga hamasi emas. ko'pincha, biz bir qator narsalarni to'playmiz, so'ngra eng katta kalit bilan ishlov beramiz, keyin ko'proq narsalarni to'playmiz, so'ngra hozirgi eng katta kalit bilan ishlov beramiz va hokazo. bunday muhitda tegishli ma'lumotlar turi ikkita amalni qo'llab-quvvatlaydi: maksimal miqdorni oʻchirish va joylashtirish. bunday ma'lumotlar turi ustivor navbat deb nomlanadi. ustivor navbatlar odatdagi navbat yoki stek ma'lumotlar tuzilmasiga o'xshash abstrakt ma'lumotlar turi bo'lib, unda har bir element qo'shimcha ravishda bogʻliq bo'lgan "ustivorlikka" ega. ustivor navbatda yuqori ustivor element past ustivor elementdan oldin xizmat qiladi. ustivor navbatlar ko'pincha uyum (kucha) bilan amalga oshirilsa-da, ular konseptual jihatdan uyumlardan farq qiladi. ustivor navbat - bu "ro'yxat" yoki "karta" ga o'xshash narsa; ro'yxat bogʻlangan ro'yxat …

2 / 18

elementning ustivor qiymatini o'zgartiradi 5) merge - ikkita navbatni bittaga birlashtiradi 1.1 binar uyum (kucha) - piramida (binary heap). binar uyum (binary heap) bu quyidagi shartlarni qanoatlantiradigan binar daraxtdir: - har qanday uchning ustivorligi, uning avlodlarining ustivorligidan 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). max 1-rasm. o’smaydigan piramida max-heap har qanday uchning ustuvorligi avlodlarning ustuvorligidan kichik emas 2-rasm. kamaymaydigan piramida min-heap har qanday uchning ustuvorligi avlodlarning ustuvorligidan katta e mas ii bob. brodala-okasaki uyumi haqida boshlang'ich tushunchalar brodal va okasakining priority queue kaskadli havolalarsiz binomial to'plamdan foydalanishga , minimal elementni qo'shishga va ma'lumotlarning strukturaviy yuklash g'oyasiga asoslangan . birinchisi sizga imkon beradii n s e r torqasidao ( 1 ), ikkinchisi uchun minimal elementni olish imkonini beradio ( 1 ), va uchinchi - amalga oshirish imkonini beradim e r g e orqasidao ( 1 ). …

3 / 18

ir qiymat qiymatlardan birida saqlanaditm i n. operatsiyalar birlashtirish birlashtirish kamida ikkita qiymatni tanlash orqali amalga oshiriladitm i n. ushbu element to'pning yuqori qismiga aylanadi. bu, agar kerak bo'lsa, uni istalgan vaqtda doimiy vaqtda ko'rsatishga imkon beradi. operatsiya yordamida yig'ma tuzilmaga yana bir kattaroq element kiritiladii n s e r t. bpq merge( , ): if x )> else return )> bu yergai n s e r tu ustuvor navbatga qo'shilmoqda. agar u ishlayotgan bo'lsao ( 1 ), bum e r g euchun ishlaydio ( 1 ). kiritmoq bu yangi yaratishb pqvam e r g eu asosiy daraxt bilan. bpq insert( , y:int): return merge( , singleton(y)) aslida, operatsiyai n s e r t- xuddi shum e r g e: uchun nol darajali daraxt yaratilgano ( 1 ), va keyin u asosiy bilan ham birlashadio ( 1 ). getmin buni qilish oson, chunkib pqminimal darajada ushlab turadi. int getmin( ): …

4 / 18

um birinchi bo'lib shu yerdan kirish mumkin bo'lgan qog'ozda tasvirlangan . ushbu dastur asl tavsifga iloji boricha yaqinroq amal qiladi, lekin kodda tushuntirilgan bir nechta farqlar/noaniq fikrlar mavjud. old shartlar keyinchalik harakat qilishni xohlaydigan kishi tanishishi kerak umuman uyumlar va binomial uyum (menda ushbu omborda go dan foydalangan holda dastur bor .) siz ushbu omborda mavjud bo'lgan narsalarni tushunishga harakat qilishingiz mumkin, ammo menimcha, bu tushunchalar bilan tanishish sizga vaqtni osonroq o'tkazishga yordam beradi. brodal-okasaki uyasi ushbu ma'lumotlar strukturasi binomial to'pning qattiq o'zgartirilgan versiyasidir; insert() ni o(1) da bajarishi uchun boshqa pastki daraxt bog'lash mexanizmi kiritilgan. oddiy binomial to'pda o(logn) ni oladi. bu variant "skew-binomial heap" deb ataladi. minimal elementni ushlab turadigan ildiz tugunini qo'shish. merge() ni o(1) da bajarishi uchun maʼlumotlar strukturasi oʻzini oʻzida saqlashga ruxsat berilgan. skew-binomial va oddiy binomial uyumlarda o(logn) ni oladi. ushbu uchta modifikatsiya bizga asimptotik jihatdan optimal ma'lumotlar strukturasini beradi, ya'ni biz boshqa operatsiyalar …

5 / 18

ladi. haqiqiy pop() operatsiyasi (binomial to'pdagi kabi) allaqachon o(logn) vaqtini oladi. 3 logn yoki 50 logn amalni bajarishimiz muhim emasligi sababli , "o" belgisi ostida ularning barchasi o(logn) dir. ushbu kichik buzg'unchilik orqali biz asimptotik optimallikka erishamiz, bunda pop() dan boshqa hamma narsa o(1) ostida amalga oshiriladi. ko'rib turganingizdek, biz bu erda bajarilgan ish hajmini kamaytirmaymiz, shunchaki ularni bir xil soyabon ostiga surib qo'yamiz, shunda jadval chiroyli va chiroyli ko'rinadi. shu sababli, men mualliflarning ushbu ma'lumotlar tuzilmasi amaliy qiziqish uyg'otmasligini ta'kidlaganiga qo'shilaman, ammo bunday asimptotik ishlash mumkinligiga nazariy misol bo'lib xizmat qiladi. funktsional va imperativ qog'ozda brodal-okasaki uyasi funktsional amalga oshirilgan. bu erda men amalga oshirishni imperativ tilda (go) qildim, shuning uchun ba'zi tushunchalar to'g'ridan-to'g'ri tarjima qilinmasligi mumkin. boshqotirmalar ushbu ma'lumotlar strukturasini tushunganingizdan so'ng, siz u bilan o'ynashingiz mumkin ishlash uchun optimallashtirish. ushbu dastur dahshatli darajada samarasiz va optimallashtirish mumkin bo'lgan ko'plab fikrlar mavjud. koddagi sharhlar sifatida ba'zi savollarni qoldirdim. …

Ko'proq o'qimoqchimisiz?

Barcha 18 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"uyum (kucha) - saralash (binary heap)" haqida

uyum (kucha) - saralash (binary heap). reja 1 uyum (kucha) - piramida (binary heap). 2 asimptotik optimallik. 3 uyma tartiblash. 4 uyumni saralash algoritmi. ko'pgina ilovalar kalitlarga ega bo'lgan elementlarni qayta ishlashni talab qiladi, lekin ular to'liq tartibda va birdaniga hamasi emas. ko'pincha, biz bir qator narsalarni to'playmiz, so'ngra eng katta kalit bilan ishlov beramiz, keyin ko'proq narsalarni to'playmiz, so'ngra hozirgi eng katta kalit bilan ishlov beramiz va hokazo. bunday muhitda tegishli ma'lumotlar turi ikkita amalni qo'llab-quvvatlaydi: maksimal miqdorni oʻchirish va joylashtirish. bunday ma'lumotlar turi ustivor navbat deb nomlanadi. ustivor navbatlar odatdagi navbat yoki stek ma'lumotlar tuzilmasiga o'xshash abstrakt ma'lumotlar turi bo'lib, unda har bir element qo...

Bu fayl DOC formatida 18 sahifadan iborat (94,5 KB). "uyum (kucha) - saralash (binary heap)"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: uyum (kucha) - saralash (binary… DOC 18 sahifa Bepul yuklash Telegram