logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Brodala – Okasaki uyumi

Brodala – Okasaki uyumi

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

911.275390625 KB
Ko'chirib olish
Brodala – Okasaki uyumi MUNDARIJA: KIRISH …………………………………………………………………………… 3 1. Brodal va Okasakining ustuvor navbati ……………………………………… 5 1.1 Eng qiyin operatsiya deleteMin ……………………………………………… 6 1.2. Brodalning ma'lumotlar strukturasi ………………………………………...9 2. Ikkilamchi navbatlar ………… … …………………… … …… … …… ……… 12 3. Global ildiz qo'shish … ……………………………… … ………… ………… 20 3.1. AddRoot optimallashtirish … ……………………………… … ………… ... 22 3.2. Bootstrapping ustuvor navbatlar … ……………………………… … ……24 3.3. Optimallashtirish … …… … …… … ……………………………… … ……..28 4. Tegishli ish va muhokama ……… … …… … …… … ………………………… 30 4.1. Munozara ……… … …… …… …… …… ……… … ………………………… 31 XULOSA ……………………………………………………………………….... 34 FOYDALANILGAN ADABIYOTLAR ……………………………………… 35 1 Kirish Brodal Okasaki (ingl. Brodal's and Okasaki's Priority Queue)-kaskadli havolalarsiz binomial qoziqdan foydalanish, minimal element qo'shish va ma'lumotlar strukturasini yuklash g'oyasiga asoslangan. Birinchisi sizga imkon beradi insert uchun O(1), ikkinchisi sizga minimal elementni olish imkonini beradi O(1), uchinchisi esa bajarishga imkon beradi merge uchun O(1). Minimalni olib tashlash quyidagilar uchun ishlaydi O(logN) eng yomon holatda. Ushbu hisob- kitoblar taqqoslashga asoslangan barcha ustuvor navbatlar orasida asimptotik jihatdan maqbuldir. Bu chegaralar asimptotikdir barcha taqqoslashga asoslangan ustuvor navbatlar orasida optimal. Brodalning ma'lumotlar strukturasi sof funktsional sozlamalarga ega. Bunda Vuillemin ma'lumotlar strukturasini soddalashtirish va uning binomial navbatlar bilan aloqasini aniqlashtirish O(log n) vaqtida barcha to'rtta operatsiyani qo'llab-quvvatlaydi. Xususan, biz amalga oshirishni binomial navbatlardan uch bosqichda olamiz: birinchidan, biz kaskadli havolalar imkoniyatidan foydalanib, qo'shimchaning ishlash vaqtini O(1) ga qisqartiramiz; ikkinchidan, minimal elementni ushlab turish uchun global ildiz qo'shish orqali findMin ning ishlash vaqtini O(1) ga qisqartiramiz; va nihoyat, ustuvor navbatlar boshqasini o'z ichiga olishiga ruxsat berish orqali qotishning ishlash vaqti O(1) ga kamaytiramiz. Ushbu bosqichlarning har biri ML uslubidagi funktorlar yordamida ifodalanadi. Ma'lumotlar-strukturali yuklash deb nomlanuvchi so'nggi 2 transformatsiya qiziqarli yuqori tartibli funktorlar va rekursiv tuzilmalarni qo'llashdir. Sof funktsional ma'lumotlar tuzilmalari imperativ ma'lumotlar tuzilmalaridan kamida ikki jihatdan farq qiladi. Birinchidan, ko'plab imperativ ma'lumotlar tuzilmalari samaradorlik uchun halokatli topshiriqlarga tayanadi, holbuki sof funktsional ma'lumotlar tuzilmalariga halokatli topshiriqlardan foydalanish taqiqlanadi. Ikkinchidan, sof funktsional ma'lumotlar tuzilmalari avtomatik ravishda doimiy ya'ni yangilanishdan keyin ikkalasi ham ma'lumotlar strukturasining yangi va eski versiyalari keyingi ma'lumotlar uchun mavjud kirish va yangilanishlardir. Bundan farqli o'laroq, imperativ ma'lumotlar tuzilmalari deyarli har doim vaqtinchalik bo'ladi, ya'ni yangilanishdan keyin faqat yangi ma'lumotlar strukturasi versiyasi mavjud. Ko'pgina hollarda, algoritm matnlarida tasvirlanganlar kabi ma'lumotlar tuzilmalari funktsional dasturchilarga oddiygina foydalanishga to'sqinlik qiladi. Shunday qilib, samarali sof funktsional ma'lumotlar tuzilmalarini loyihalash katta ahamiyatga ega. Funktsional dasturchilar uchun nazariy va amaliy qiziqish, shuningdek doimiy bo'lgan holatlar uchun imperativ dasturchilarga kelsak ma'lumotlar tuzilishi talab qilinadi. Ustuvor navbat kompyuter dasturlashda asosiy abstraksiyadir, faqat lug'at orqali muhimligi oshib ketgan ketma-ketlik. Ustuvor navbatlarning ko'plab tatbiqlari amalga oshirilishi yillar davomida taklif qilingan, kichik namuna : (Williams, 1964; Kran, 1972; Vuillemin, 1978; Fredman va Tarjan, 1987; Brodal, 1996). Biroq, bularning barchasi faqat imperativ ustuvor navbatlarni hisobga oladi. Juda sof funktsional ustuvor navbatlar haqida kam yozilgan. Bizning bilim, faqat Paulson (1991), Kaldewaij va Schoenmakers (1991), Schoenmakers (1992) va King (1994) ustuvorliklarga aniq munosabatda bo'lishdi. 3 1. Brodal va Okasakining ustuvor navbati Binomli navbatlar ustuvor navbatning nafis shaklidir. Vuillemin (1978) va Braun (1978) tomonidan keng o'rganilgan. Garchi ular binomial navbatlarni faqat imperativ sharoitda ko'rib chiqqan bo’lsalar ham, King (1994) binomial navbatlar funktsional sharoitda teng darajada yaxshi ishlashini ko'rsatdi. Ushbu bo'limda biz binomial navbatlarni qisqacha ko'rib chiqamiz . Binomli navbatlar ibtidoiy deb nomlanuvchi ob'ektlardan iborat binomial daraxtlar. Binom daraxtlari induktiv ravishda quyidagicha aniqlanadi: • 0-darajali binom daraxti yagona tugundir. • r+1 darajali binom daraxti ikkita binomni bog‘lash orqali hosil bo‘ladi. r-darajali daraxtlar, bir daraxtni ikkinchisining eng chap bolasi qilib oladi. Ushbu ta'rifdan r darajali binomial daraxt ekanligini ko'rish oson aniq 2r tugunni o'z ichiga oladi. Ikkinchi, ekvivalent ta'rifi. Ba'zan qulayroq bo'lgan binomial daraxtlar: binomial daraxt r rank - r bolalar t1 ...tr bo'lgan tugun, bu erda har bir ti binomdir r - i darajali daraxt. Tugunlar bo'yicha umumiy tartibni nazarda tutsak, binomial daraxt deyiladi har bir tugun ≤ har bir avlodi bo'lsa, yig'ma tartibli. Saqlash uchun Ikki uyin tartibli daraxtlarni bog'lashda yig'ish tartibini qilamiz ildizi kattaroq daraxt - kichikroq ildizli daraxtning bolasi, bilan aloqalar o'zboshimchalik bilan uziladi. 4 Bir binomial binomial navbat, bu erda yig'ilgan tartibli binomial daraxtlar o'rmonidir ikkita daraxt bir xil darajaga ega emas. Chunki binomial daraxtlarning o'lchamlari bor 2 r shakldagi, n o'lchamdagi binomial navbatdagi daraxtlarning qatorlari ning ikkilik ko'rinishidagilarga ko'ra taqsimlanadi. Masalan, 21 o'lchamdagi binomial navbatni ko'rib chiqing. Binar 21 ning ifodasi 10101 va binomial navbatda daraxtlar mavjud 0, 2 va 4-darajali (mos ravishda 1, 4 va 16 o'lchamdagi). E'tibor bering, a n o lchamdagi binomial navbat ko pi bilanʻ ʻ log2(n+1) daraxtini o z ichiga oladi. Endi biz binomial navbatlardagi ʻ operatsiyalarni tasvirlashga tayyormiz. Binomial navbatdagi barcha daraxtlar yig'indisi bo'lganligi sababli, biz buni bilamiz binomial navbatdagi minimal element birining ildizi daraxtlardir. Ushbu minimal elementni O(log n) vaqtida skanerlash orqali topishimiz mumkin ildizlar orqali. Navbatga yangi element qo'shish uchun birinchi navbatda yangi singleton daraxtini yarating (ya'ni, 0-darajali binomial daraxt). Biz keyin bizgacha martabani oshirish tartibida mavjud daraxtlar orqali qadam yo'qolgan darajani toping, biz borar ekanmiz, teng darajadagi daraxtlarni bog'laymiz. Kiritish elementni binomial navbatga qo'shish bittani qo'shishga to'g'ri keladi ikkilik raqam, har bir havola tashishga mos keladi. Eng yomon hol bu n = 2k − 1 o lchamdagi navbatga kiritish ʻ bo lib, jami k ni havolalar va O(log n) vaqti talab qiladi. ikkita navbatni ʻ birlashtirish uchun ikkilik qo'shishga o'xshashlik ham amal qiladi. Biz ikkala navbatning daraxtlari orasidan o'tamiz. Bir marta yana, har bir havola bir tashish mos keladi. Buning uchun O (log n) vaqtni ham talab qiladi. 1.1. Eng qiyin operatsiya bu deleteMin . Biz birinchi navbatda daraxtni topamiz minimal ildiz va uni navbatdan olib tashlaymiz. Biz ildizni olib tashlaymiz, lekin keyin o'z farzandlarini navbatga qaytarishi kerak. Biroq, bolalar o'zlari to'g'ri binomial navbatni tashkil qiladi (ya'ni, bir xil darajadagi ikkita daraxt bo'lmagan tepalikli binomial daraxtlar o'rmoni) va shuning uchun navbatning qolgan daraxtlari bilan birlashtirilishi mumkin. Ikkala topilma daraxtni olib 5 tashlash va bolalarni navbatga qaytarish O(log n) vaqt, jami O(log n) vaqt talab etadi. Elementlar va belgilangan turdagi elementlarni o'z ichiga olgan ustuvor navbatlar tuzilishini ishlab chiqaradi. Ushbu amalga oshirishning ikkita jihati qo'shimcha tushuntirishga loyiqdir. Birinchidan, qo'shimchaning qarama-qarshi talablari va bog'lanish deyarli barcha uchun umumiy bo'lgan chalkash nomuvofiqlikka olib keladi functor Binomial Queue (E: ORDERED): PRORITALIK NAVBAT = struct structure Elem = E type Rank = int datatype Tree = Node of Elem.T × Rank × Tree list type T = Tree list ( ∗ auxiliary functions ∗ ) fun root (Node (x,r,c)) = x fun rank (Node (x,r,c)) = r fun link (t1 as Node (x1,r1,c1), t2 as Node (x2,r2,c2)) = ( ∗ r1 = r2 ∗ ) if Elem.leq (x1, x2) then Node (x1,r1+1,t2 :: c1) else Node (x2,r2+1,t1 :: c2) fun ins (t, [ ]) = [t] | ins (t, t0 :: ts)= ( ∗ rank t ≤ rank t0 ∗ ) if rank t < rank t 0 then t :: t0 :: ts else ins (link (t, t0), ts) val empty =[] fun isEmpty ts = null ts fun insert (x, ts) = ins (Node (x,0,[ ]), ts) fun meld ([ ], ts) = ts | meld (ts, [ ]) = ts | meld (t1 :: ts1, t2 :: ts2) = if rank t1 < rank t2 then t1 :: meld (ts1, t2 :: ts2) else if rank t2 < rank t1 then t2 :: meld (t1 :: ts1, ts2) 6 else ins (link (t1, t2), meld (ts1, ts2)) exception EMPTY fun findMin [ ] = raise EMPTY | findMin [t] = root t | findMin (t :: ts) = let val x = findMin ts in if Elem.leq (root t, x) then root t else x end fun deleteMin [ ] = raise EMPTY | deleteMin ts = let fun getMin [t]=(t, [ ]) | getMin (t :: ts) = let val (t0, ts0) = getMin ts in if Elem.leq (root t, root t0) then (t, ts) else (t0, t :: ts0) end val (Node (x,r,c), ts) = getMin ts in meld (rev c, ts) end end Bu - binomial navbatlarni amalga oshiruvchi funktordir. Binomial navbatlarning qo'shimchalari. Binomial navbatdagi daraxtlar qo'shish operatsiyasini samarali qo'llab-quvvatlash uchun darajani oshirish tartibida saqlanadi. Boshqa tomondan, binomial daraxtlarning bolalari havola ishini qo'llab- quvvatlash uchun darajaning pasayish tartibida samarali saqlanadi. Bu nomuvofiqlik bizni DeleteMin paytida o'chirilgan tugun bolalarni o'zgartirishga majbur qiladi. Ikkinchidan, aniqlik uchun, har bir tugun o'z darajasini o'z ichiga oladi. Haqiqiy amalga oshirishda esa, faqat ildizlar saflarini saqlab qolar edi. Boshqa barcha tugunlarning darajalari o'ziga xosdir ota-onalarining martabalari va o'rtasidagi o'rinlari bilan belgilanadi ularning ukalari. King (1994) muqobil vakillikni tasvirlaydi ular uchun to'ldiruvchilarni joriy etish evaziga barcha darajalarni yo'q qiladi. Ularning ikkilik ko'rinishidagi nolga mos keladigan darajalar navbatning o'lchami. 7 Biz quyidagi operatsiyalarni qo'llab-quvvatlaydigan ustuvor navbatlarni ko'rib chiqamiz: findMin (q) q navbatining minimal elementini qaytaring. insert (x, q) X elementini q navbatiga kiriting. meld (q1, q2) q1 va q2 navbatlarini bitta navbatga birlashtiring. deleteMin (q) q navbatining minimal elementidan voz keching. Bundan tashqari, ustuvor navbatlar bo'sh qiymatni ifodalovchi bo'sh qiymatni beradi signature ORDERED = sig type T ( ∗ type of ordered elements ∗ ) val leq : T × T → bool ( ∗ total ordering relation ∗ ) end signature PRIORITY QUEUE = sig structure Elem : ORDERED type T ( ∗ type of priority queues ∗ ) val empty : T val isEmpty : T → bool val insert : Elem.T × T → T val meld : T × T → T exception EMPTY val findMin : T → Elem.T ( ∗ raises EMPTY if queue is empty ∗ ) val deleteMin : T → T ( ∗ raises EMPTY if queue is empty ∗ ) end navbat va predikat bo'sh. Oddiylik uchun biz bo'sh narsalarni e'tiborsiz qoldiramiz 8 haqiqiy kodni taqdim etishdan tashqari navbatlar. Ushbu ustuvor navbatlar uchun standart ML imzosi ko'rsatilgan. Brodal (1995) yaqinda O (1) eng yomon holatdan tashqari barcha bu operatsiyalarni qo'llab-quvvatlash uchun birinchi imperativ ma'lumotlar strukturasini taqdim etdi. DeleteMin, bu O(log n) eng yomon vaqtni talab qiladi. Bir necha oldingi ilovalar, ayniqsa Fibonachchi to'plamlari (Fredman va Tarjan, 1987), bu chegaralarga erishgan edi, lekin amortizatsiya qilingan, aksincha eng yomoni, ma'nosi. Bularni saralashni qisqartirish orqali ko'rsatish oson chegaralar barcha taqqoslashga asoslangan ustuvor navbatlar orasida asimptotik jihatdan optimaldir - deleteMin-dagi chegarani bu holda kamaytirish mumkin emas. findMin, insert va/yoki birlashmadagi chegaralarni bir vaqtning o'zida oshirish. 1.2. Brodalning ma'lumotlar strukturasini moslashtirish juda oddiy rekursiv-sekinlashuvni birlashtirib, sof funksional sozlamaga Kaplan va Tarjan (1995) texnikasi ikki tomonlama navbatlarning sof funktsional amalga oshirilishi (Hud, 1982; Okasaki, 1995c). Biroq, bu yondashuv kamida ikkita nuqsondan aziyat chekadi, biri amaliy va bitta pedagogik. Birinchidan, ham rekursiv sekinlashuv, ham ikki tomonlama navbatlar ahamiyatsiz bo'lmagan qo'shimcha xarajatlarni o'z ichiga oladi, shuning uchun natijada ma'lumotlar tuzilishi amalda juda sekin (asimptotik optimal bo'lsa ham). Ikkinchi, olingan dizaynni tushuntirish va tushunish qiyin. Dizayn tanlovlari bir-biriga aralashib ketgan va maqsadni ko'rish qiyin har birining hissasi. Bundan tashqari, boshqa ustuvorlik bilan munosabat navbat dizaynlari xiralashgan. Shu ma'lumotlar tuzilishi sabablarga ko'ra biz Brodalni moslashtirishga bilvosita yondashamiz. Birinchidan, biz Brodal ma'lumotlaridagi dizayn tanlovlarini ajratamiz va har birini imperativ emas, balki funktsional muhitda qayta ko'rib chiqing. Bu bizga rekursiv sekinlashuvni oddiyroq bilan almashtirishga imkon beradi. Okasakining tasodifiy kirish ro'yxatidan olingan texnika (1995b) va ikki tomonlama navbatlarga bo'lgan ehtiyojni butunlay yo'q qilish. Keyin, Vuilleminning (1978) binomial navbati - taniqli oldingi narsadan boshlab, biz har 9 bir modifikatsiyani birma-bir qayta kiritamiz. Bu ham ma'lumotlar strukturasini soddalashtiradi, ham uning boshqalar bilan aloqasini aniqlaydi ustuvor navbat dizaynlari. Biz binomial navbatlarni ko'rib chiqishdan boshlaymiz, ular O (log n) vaqtida barcha to'rtta asosiy operatsiyalarni qo'llab-quvvatlaydi. Keyin biz ma'lumotlar tuzilmamizni olamiz. Binomial navbatlardan uch bosqichda. Birinchidan, biz yugurish tezligini kamaytiradigan egilgan binomial navbatlar deb ataladigan binomial navbatni tasvirlaymiz. Kaskadli ulanishlar imkoniyatini yo'q qilish orqali O (1) ga qo'shish vaqti. Ikkinchidan, a qo'shish orqali findMinning ishlash vaqtini O(1) ga qisqartiramiz minimal elementni ushlab turish uchun global ildiz. Uchinchidan, biz Buchsbaum va boshqalarning texnikasini qo'llaymiz. (Buchsbaum va boshq., 1995; Buchsbaum & Tarjan, 1995) ma'lumotlarning strukturaviy yuklash deb nomlanadi, bu esa ma'lumotlarni kamaytiradi ustuvor navbatlarni o'z ichiga olishiga ruxsat berish orqali O(1) ga qotishning ishlash vaqti boshqa ustuvor navbatlar. Ushbu bosqichlarning har biri ML funktorlar uslubi yordamida ifodalanadi. Oxirgi transformatsiya, ma'lumotlarning strukturaviy yuklanishi yuqori tartibli funktorlar va rekursiv tuzilmalarning qiziqarli qo'llanilishi. Bir nechta mumkin bo'lgan optimallashtirishlarni tavsiflab bo'lgach, biz xulosa qilamiz tegishli ishlar va kelajakdagi ishlar haqida qisqacha muhokamalar. 1 - rasm: 0-3 darajali binom daraxtlari 10 2. Ikkilamchi navbatlar Binomial navbatlarning skew deb ataladigan variantini tasvirlaymiz. Binomial navbatlar, bu O (1) eng yomon vaqt vaqtida kiritishni qo'llab- quvvatlaydi. Binomial navbatlar bilan bog'liq muammo bitta elementni a ga kiritishdir navbat ulanishlarning uzun kaskadiga olib kelishi mumkin, xuddi a ga bitta qo'shish kabi ikkilik raqam tashishlarning uzoq kaskadiga olib kelishi mumkin. Biz kamaytirishimiz mumkin texnikani qarzga olish orqali ko'pi bilan bitta havolaga qo'shish narxi tasodifiy kirish ro'yxatidan (Okasaki, 1995b). Tasodifiy kirish ro'yxatlari qiyshiq ikkilik sonlar deb ataladigan variantli sanoq sistemasiga asoslangan (Myers, 1983), bunda bitta qo'shish ko'pi bilan bitta tashishga olib keladi. Egri ikkilik sonlarda k-raqam 2k+1−¿ 1 ni ifodalaydi, aksincha oddiy ikkilik sonlardagi kabi 2 k dan ortiq. Har bir raqam nol teng bitta, bundan tashqari eng past 11 noldan farqli raqam ikkita bo'lishi mumkin. Masalan; misol uchun, 92 - 002101 deb yoziladi (birinchi eng kichik raqam). Tashish qachon sodir bo'ladi nolga teng bo'lmagan eng kichik raqami ikkita bo'lgan songa bitta qo'shish. Misol uchun, 1 + 002101 = 000201. Keyingi yuqori raqam ikkita bo'lmasligi kafolatlanganligi sababli, faqat bitta tashish kerak. Binamial navbatlar binomial daraxtlardan tashkil topgani kabi, qiyshiq binomial navbatlar ham qiyshiq binomial daraxtlardan iborat. Egri binomial daraxtlar induktiv ravishda quyidagicha aniqlanadi: • 0-darajali qiyshaygan binomial daraxt yagona tugundir. 2 - rasm. Binomilal daraxtni qurishning 3 xil uslubi. Egri binomial daraxtni qurishning uchta usuli daraja r + 1. (a) oddiy havola. (b) A tipidagi egilgan havola. (c) a turidagi B qiyshiq l. • r + 1 darajali qiyshiq binomial daraxt uchta usuldan birida hosil bo'ladi: – oddiy havola, r-darajali qiyshiq binomial daraxtni eng chapga aylantiradi r darajali boshqa qiyshiq binom daraxtining bolasi; – r-darajali ikkita qiyshaygan binomial daraxtni hosil qiluvchi A tipidagi egilgan bog‘lanish 0-darajali qiyshiq binomial daraxtning bolalari; yoki – 0 va darajali qiyshaygan binomial daraxtni hosil qiluvchi B tipidagi egilgan havola darajali qiyshiq binomial daraxt r boshqasining eng chap bolalarining qiyshiq binomial daraxti 12 2 - rasmda uch xil havolalar ko'rsatilgan. E'tibor bering, A turi va r = 0 bo‘lganda B tipidagi qiyshiq bog‘lanishlar ekvivalent bo‘ladi. Oddiy binomial daraxtlar va mukammal muvozanatli binar daraxtlar qiyshiq binomialning maxsus holatlaridir faqat oddiy havolalar va A tipidagi egri havolalarga ruxsat berish orqali olingan daraxtlar, mos ravishda. r-darajali qiyshiq binom daraxti butunlay qurilgan Skew links (turi A yoki B tipi) aniq 2 r+1 - 1 tugunni o'z ichiga oladi, lekin, umuman olganda, r-darajali t qiyshiq binomial daraxtning o'lchami bilan chegaralanadi 2r ≤ |t| ≤ 2r+1 − 1. Bundan tashqari, qiyshiq binomial daraxtning balandligi darajasiga teng. Yana bir bor, ikkinchi, ekvivalent ta'rif mavjud: r > 0 darajali qiyshiq binomial daraxt - 2 minggacha bolali tugun s 1 t 1 ... s k t k (1 ≤ k ≤ r), bunda har bir t i darajali qiyshiq binomial daraxtdir. r - i va har bir s i 0-darajali qiyshiq binomial daraxtdir, bundan tashqari s k ga ega r − k darajasi (faqat k = r bo'lganda 0 bo'ladi). Bundan tashqari, har bir s i ixtiyoriy bu s i faqat k = r bo'lganda ixtiyoriydir. Biroz chalkash bo'lsa-da, bu ta'rif tabiiy ravishda a daraxtni qurishning uchta usulidan kelib chiqadi. Har bir s k t k juftligi A tipidagi egilish havolasi orqali ishlab chiqariladi va 13 3 – rasm. 2-darajali qiyshiq binomial daraxtlarning o'n ikkita mumkin bo'lgan shakllari. Chiziqli qutilar har bir siti juftini o'rab oladi. Si ti juftligi (i<k) B tipidagi egilish havolasi orqali ishlab chiqariladi. Har bir ti holda mos keladigan si oddiy havola orqali ishlab chiqariladi. Oddiy binomial daraxtlardan farqli o'laroq, egilgan binomial daraxtlar juda ko'p turli xil shakllarga ega bo'lishi mumkin. Masalan, 3- darajali qiyshiq binomial daraxtlarning o'n ikkita mumkin bo'lgan shakllari 3 - rasmda ko'rsatilgan. Egri binomial daraxt, agar har bir tugun ≤ o'zining har biri avlodlari bo'lsa, yig'ma tartibli hisoblanadi. Oddiy havola paytida yig'ish tartibini saqlab qolish uchun biz ildizi kattaroq daraxt kichikroq ildizli daraxtning bolasi qilamiz. Egri bog'lanish paytida biz ikkita daraxtni eng kichik ildizga ega bo'lgan daraxtning kattaroq ildizli bolalar qilamiz. Agar A tipidagi egilish havolasini bajaramiz 0-darajali daraxt eng kichik ildizga ega va agar ulardan biri bo'lsa, B tipidagi egilgan havola r-darajali daraxtlar eng kichik ildizga ega. Egri binomial 14 navbat - yig'ma tartibli qiyshiq binomial o'rmonidir. Ikkita daraxt bir xil darajaga ega bo'lmagan daraxtlar, ehtimol ikkitadan tashqari eng kichik o'rinli daraxtlar. Bir xil darajadagi egilgan binomial daraxtlar bo'lishi mumkin turli o'lchamlarga ega, darajalarni taqsimlashning bir necha yo'li bo'lishi mumkin har qanday o'lchamdagi navbat uchun. Masalan, qiyshiq binomial navbat 4-o'lchamdagi bitta 2-darajali 4- o'lchamdagi daraxtni o'z ichiga olishi mumkin; 1-darajali ikkita daraxt, har biri 2 o'lchamli; 3-o lchamdagi 1-darajali daraxt va 0-darajali daraxt; yoki 1-darajaliʻ daraxt 2 o'lchamli va ikkita 0-darajali daraxtlar. Biroq, daraxtlarning maksimal soni navbatda hali ham O (log n). Endi biz skew binomial navbatlar ustidagi amallarni tasvirlashga tayyormiz. FindMin va birlashtirish operatsiyalari deyarli o'zgarmadi. Kimga qiyshiq binomial navbatdagi minimal elementni toping, biz shunchaki skanerlaymiz ildizlar orqali, O(log n) vaqtini oladi. Ikki navbatni birlashtirish uchun biz qadam qo'yamiz. Ikkala navbatning daraxtlari bo'ylab ortib borayotgan darajalar tartibida, har doim teng bo'lgan ikkita daraxt topilganda oddiy bog'lanishni (qiyshaygan havola emas!) bajaramiz. Yana bir bor, bu O (log n) vaqtini talab qiladi. Oddiy binomialga nisbatan qiyshiq binomial navbatlarning katta afzalligi navbatlar shundan iboratki, biz endi O (1) vaqtida yangi elementni kiritishimiz mumkin. Biz birinchi yangi singleton daraxtini yarating (ya'ni, 0-darajali egilgan binomial daraxt). Biz keyin navbatdagi ikkita eng kichik daraxtning saflarini tekshiring. Agar ikkalasi ham daraxtlar r darajasiga ega, keyin biz bu ikki daraxtni yangi daraja bilan bog'laymiz. Yangi darajali r+1 daraxtini olish uchun 0 daraxti. Biz bilamizki, bundan ortiq bo'lishi mumkin emas mavjud bir darajali r + 1 daraxtdan ko'ra, va bu eng kichik darajadir yangi navbatda, shuning uchun biz oddiygina yangi daraxtni navbatga qo'shamiz. Agar navbatdagi ikkita eng kichik daraxt turli darajalarga ega, keyin biz oddiygina 15 navbatga yangi 0-darajali daraxt qo'shing. Chunki ko'pi bilan bittasi bor edi 0- darajali mavjud daraxt, yangi navbat ko'pi bilan ikkita daraxtni o'z ichiga oladi eng kichik daraja. Ikkala holatda ham, biz tugatdik. Shunga qaramay, deleteMin eng murakkab operatsiya hisoblanadi. Avval topamiz va daraxtni minimal ildiz bilan olib tashlang. Ildizni tashlaganingizdan so'ng, biz uning bolalarini ikki guruhga ajratamiz, 0 darajali va o'sha rank > 0 bilan. S k va t k dan boshqa har bir si 0 va har bir darajaga ega ti darajasi > 0 ga ega. k = r va S k va t k darajalari ikkalasi ham 0 ga teng. k<r bo'lganda ikkalasi > 0. E'tibor bering, har bir 0-darajali bola bittadan iborat element. Darajasi > 0 bo lganʻ bolalar to g ri qiyshiq binomni tashkil qiladi. Navbat, shuning uchun biz bu ʻ ʻ bolalarni navbatdagi qolgan daraxtlar bilan birlashtiramiz. Nihoyat, biz 0-darajali bolalarning har birini qayta kiritamiz. Ushbu qadamlarning har biri O(log n) vaqtni talab qiladi, shuning uchun talab qilinadigan umumiy vaqt O(log n) dir. Binomli navbat funktori singari, bu funktor tartiblangan elementlarning turini ko'rsatuvchi tuzilmani oladi va hosil qiladi. Belgilangan turdagi elementlarni o'z ichiga olgan ustuvor navbatlar tuzilishi. Yana bir bor, daraxtlar ro'yxati turli xil tartibda saqlanadi. Navbatdagi daraxtlar ortib borayotgan tartibda saqlanadi daraja (birinchi ikkita daraxt bir xil darajaga ega bo'lishidan tashqari), lekin qiyshaygan binomial daraxtlarning bolalari yanada murakkab holatda saqlanadi : functor SkewBinomialQueue (E : ORDERED) : PRIORITY QUEUE = struct structure Elem = E type Rank = int datatype Tree = Node of Elem.T × Rank × Tree list type T = Tree list ( ∗ auxiliary functions ∗ ) fun root (Node (x,r,c)) = x 16 fun rank (Node (x,r,c)) = r fun link (t1 as Node (x1,r1,c1), t2 as Node (x2,r2,c2)) = ( ∗ r1 = r2 ∗ ) if Elem.leq (x1,x2) then Node (x1,r1+1,t2 :: c1) else Node (x2,r2+1,t1 :: c2) fun skewLink (t0 as Node (x0,r0, ), t1 as Node (x1,r1,c1), t2 as Node (x2,r2,c2)) = if Elem.leq (x1,x0) andalso Elem.leq (x1,x2) then Node (x1,r1+1,t0 :: t2 :: c1) else if Elem.leq (x2,x0) andalso Elem.leq (x2,x1) then Node (x2,r2+1,t0 :: t1 :: c2) else Node (x0,r1+1,[t1, t2]) fun ins (t, [ ]) = [t] | ins (t, t0 :: ts)= ( ∗ rank t ≤ rank t0 ∗ ) if rank t < rank t 0 then t :: t0 :: ts else ins (link (t, t0), ts) fun uniqify []=[] | uniqify (t :: ts) = ins (t, ts) ( ∗ eliminate initial duplicate ∗ ) fun meldUniq ([ ], ts) = ts | meldUniq (ts, [ ]) = ts | meldUniq (t1 :: ts1, t2 :: ts2) = if rank t1 < rank t2 then t1 :: meldUniq (ts1, t2 :: ts2) else if rank t2 < rank t1 then t2 :: meldUniq (t1 :: ts1, ts2) else ins (link (t1, t2), meldUniq (ts1, ts2)) val empty =[] fun isEmpty ts = null ts fun insert (x, ts as t1 :: t2 :: rest) = if rank t1 = rank t2 then skewLink (Node (x,0,[ ]),t1,t2) :: rest else Node (x,0,[ ]) :: ts | insert (x, ts) = Node (x,0,[ ]) :: ts fun meld (ts, ts0 ) = meldUniq (uniqify ts, uniqify ts0 ) exception EMPTY 17 fun findMin [ ] = raise EMPTY | findMin [t] = root t | findMin (t :: ts) = let val x = findMin ts in if Elem.leq (root t, x) then root t else x end fun deleteMin [ ] = raise EMPTY | deleteMin ts = let fun getMin [t]=(t, [ ]) | getMin (t :: ts) = let val (t0, ts0) = getMin ts in if Elem.leq (root t, root t0) then (t, ts) else (t0, t :: ts0) end fun split (ts,xs,[ ]) = (ts, xs) | split (ts,xs,t :: c) = if rank t = 0 then split (ts,root t :: xs,c) else split (t :: ts,xs,c) val (Node (x,r,c), ts) = getMin ts val (ts0, xs0) = split ([ ],[ ],c) in fold insert xs0 (meld (ts, ts0)) end end T i bolalar darajasining kamayishi tartibida saqlanadi, lekin ular 0 darajasiga ega bo'lgan s i bolalari bilan aralashtiriladi (bundan tashqari r - k darajasiga ega bo'lgan s k ). Bundan tashqari, har bir s i ixtiyoriy ekanligini unutmang (bundan tashqari, s k faqat k = r bo'lganda ixtiyoriydir). Keyinchalik biz ustuvorlik bo'yicha modul darajasidagi oddiy transformatsiyani tasvirlaymiz. FindMin ning ishlash vaqtini O(1) ga qisqartirish uchun navbatlar. Garchi bu transformatsiya har qanday ustuvor navbat moduliga qo'llanilishi mumkin, bu faqat findMin O(1) dan ko'proq narsani talab qiladigan ustuvor navbatlarda foydalidir. 18 Ko'pgina ustuvor navbatlar navbatni bitta sifatida ifodalaydi minimal element har doim topilishi uchun yig'ilgan tartibli daraxt O (1) vaqtida ildizda. Afsuski, binomial navbatlar va egilish binomial navbatlar navbatni to'plangan daraxtlar o'rmoni sifatida ifodalaydi, shuning uchun minimal elementni topish uchun barcha ildizlarni skanerlash kerak o'rmon. Biroq, biz bu o'rmonni bitta yig'indiga aylantira olamiz daraxt, shu bilan O(1) vaqtida findMin-ni qo'llab-quvvatlaydi, shunchaki a qo'shib minimal elementni ushlab turish uchun global ildiz. Umuman olganda, bu daraxt bo'lmaydi binomial yoki qiyshiq binomial daraxt bo'ling, lekin bu vaqtdan beri ahamiyatsiz global ildiz navbatning qolgan qismidan alohida ko'rib chiqiladi. The Ushbu o'zgarishlarning tafsilotlari odatiy holdir, ammo biz ularni taqdim etamiz baribir, yanada murakkab transformatsiyalar uchun isinish sifatida keyingi bo'lim. 19 3. Global ildiz qo'shish Keyinchalik biz ustuvorlik bo'yicha modul darajasidagi oddiy transformatsiyani tasvirlaymiz findMin ning ishlash vaqtini O(1) ga qisqartirish uchun navbatlar. Garchi bu transformatsiya har qanday ustuvor navbat moduliga qo'llanilishi mumkin, bu faqat findMin O(1) vaqtidan ko'proq narsani talab qiladigan ustuvor navbatlarda foydalidir. Ko'pgina ustuvor navbatlar navbatni bitta sifatida ifodalaydi. Minimal element har doim topilishi uchun yig'ilgan tartibli daraxt O (1) vaqtida ildizda. Afsuski, binomial navbatlar va egilish binomial navbatlar navbatni to'plangan daraxtlar o'rmoni sifatida ifodalaydi, shuning uchun minimal elementni topish uchun barcha ildizlarni skanerlash kerak. Biroq, biz bu o'rmonni bitta yig'indiga aylantira olamiz. Daraxt, shu bilan O(1) vaqtida findMin- ni qo'llab-quvvatlaydi, shunchaki a qo'shib minimal elementni ushlab turish uchun global ildiz. Umuman olganda, bu daraxt bo'lmaydi. Binomial yoki qiyshiq binomial daraxt bo'ling, lekin bu vaqtdan beri ahamiyatsiz. Global ildiz navbatning qolgan qismidan alohida ko'rib chiqiladi. Ushbu o'zgarishlarning tafsilotlari odatiy holdir, ammo biz ularni baribir taqdim etamiz. Elementlarni o'z ichiga olgan ibtidoiy ustuvor navbatlarning ba'zi turdagi P a berilgan a tipidagi RP a bo'lishi kerak bo'lgan ildizli ustuvor navbatlar turini aniqlaymiz RP a = {bo sh} + (a × Pʻ a ) (1) Boshqacha qilib aytadigan bo'lsak, ildizli ustuvor navbat yo bo'sh yoki juft a 20 yagona element (ildiz) va ibtidoiy ustuvor navbat. Biz har qanday bo'sh bo'lmagan ustuvorlikning minimal elementi bo'lgan invariant navbat ildizda saqlaymiz. Har bir f operatsiyasi uchun ustuvor navbatlar, f : functor AddRoot (Q : PRIORITY QUEUE) : PRIORITY QUEUE = struct structure Elem = Q.Elem datatype T = Empty | Root of Elem.T × Q.T val empty = Empty fun isEmpty Empty = true | isEmpty (Root ) = false fun insert (y, Empty) = Root (y, Q.empty) | insert (y, Root (x, q)) = if Elem.leq (y, x) then Root (y, Q.insert (x, q)) else Root (x, Q.insert (y, q)) fun meld (Empty, rq) = rq | meld (rq, Empty) = rq | meld (Root (x1, q1), Root (x2, q2)) = if Elem.leq (x1, x2) then Root (x1, Q.insert (x2, Q.meld (q1, q2))) else Root (x2, Q.insert (x1, Q.meld (q1, q2))) exception EMPTY fun findMin Empty = raise EMPTY | findMin (Root (x, q)) = x fun deleteMin Empty = raise EMPTY | deleteMin (Root (x, q)) = if Q.isEmpty q then Empty else Root (Q.findMin q, Q.deleteMin q) end f0 mos ravishda P a va RP a ustidagi amallarni bildiradi. Keyin, findMin0 (hx, qi) = x 21 insert0 (y,hx, qi) = hx, qo'shing (y,q)i agar x ≤ y bo'lsa insert0 (y,hx, qi) = hy, insert (x, q)i if y<x meld0 (hx1, q1i,hx2, q2i) = hx1, insert (x2, meld (q1, q2))i if x1 ≤ x2 meld0 (hx1, q1i,hx2, q2i) = hx2, insert (x1, meld (q1, q2))i if x2 < x1 deleteMin0 (hx, qi) = hfindMin (q), deleteMin (q)i Biz ushbu transformatsiyani standart ML funktori sifatida taqdim etamiz. U ustuvor navbat tuzilishini oladi va yangi tuzilmani ishlab chiqaradi. Ushbu optimallashtirishni o'z ichiga oladi. Skew binomialga qo'llanilganda oldingi bo'limning navbatlari, bu transformatsiya O(1) vaqtida insert va findMin ni qo'llab- quvvatlaydigan ustuvor navbat hosil qiladi. Biroq, meld va deleteMin hali ham O(log n) vaqtini talab qiladi. Agar dastur turli elementli bir nechta ustuvor navbatlarni talab qilsa, bu transformatsiyani a sifatida amalga oshirish qulayroq bo'lishi mumkin. Yuqori darajadagi funktor (MacQueen & Tofte, 1994). Birinchi tartibli funktorlar faqat tuzilmalarni olishi va qaytarishi mumkin, lekin yuqori tartibli funktorlar mumkin. Boshqa funktorlarni ham qabul qiling va qaytaring. Garchi ta'rifi Standart ML (Milner va boshq., 1990) faqat birinchi darajali funktorlarni tavsiflaydi, Standard ML ning ba'zi ilovalari, xususan Standard ML of New Jersi, yuqori darajadagi funktorlarni qo'llab-quvvatlang. BinomialQueue yoki Skew Binomial Queue kabi ustuvor navbat funksiyasi tartiblangan elementlar turini ko'rsatuvchi tuzilmani oladi va quyidagi elementlarni o'z ichiga olgan ustuvor navbatlar belgilangan tur strukturasini qaytaradi. Quyidagi yuqori tartibli funktor ustunlikka ega queue functor va ni o'z ichiga olgan ustuvor navbat funktorini qaytaradi. 3.1. AddRoot optimallashtirish. bu transformatsiya O(1) vaqtida insert va findMin ni qo'llab-quvvatlaydigan ustuvor navbat hosil qiladi. Biroq, meld va deleteMin hali ham O(log n) vaqtini talab qiladi. Agar dastur turli elementli bir nechta ustuvor navbatlarni talab qilsa, bu transformatsiyani a sifatida amalga oshirish qulayroq bo'lishi mumkin yuqori darajadagi funktor (MacQueen & Tofte, 22 1994). Birinchi tartibli funktorlar faqat tuzilmalarni olishi va qaytarishi mumkin, lekin yuqori tartibli funktorlar mumkin. Boshqa funktorlarni ham qabul qiling va qaytaring. Garchi ta'rifi Standart ML (Milner va boshq., 1990) faqat birinchi darajali funktorlarni tavsiflaydi, Standard ML ning ba'zi ilovalari, xususan Standard ML of New Jersi, yuqori darajadagi funktorlarni qo'llab-quvvatlang. Binomial Queue yoki Skew Binomial Queue kabi ustuvor navbat funksiyasi tartiblangan elementlar turini ko'rsatuvchi tuzilmani oladi va quyidagi elementlarni o'z ichiga olgan ustuvor navbatlar strukturasini qaytaradi. belgilangan tur. Quyidagi yuqori tartibli funktor ustunlikka ega queue functor va ni o'z ichiga olgan ustuvor navbat funktorini qaytaradi AddRoot optimallashtirish. functor AddRootToFun (functor MakeQ (E : ORDERED) : sig include PRIORITY QUEUE sharing Elem = E end) (E : ORDERED) : PRIORITY QUEUE = AddRoot (MakeQ (E)) E'tibor bering, bu funktor kurerli, shuning uchun u ikkita argumentlarni oladi, u aslida bitta argumentni oladi (MakeQ) va a ni qaytaradi ikkinchi argumentni qabul qiluvchi funktor (E). Ulashish cheklovi Funktor MakeQ ustuvor navbatni qaytarishini ta'minlash uchun zarur kerakli element turi bilan. Almashish cheklovisiz, MakeQ E ni e'tiborsiz qoldirishi va ba'zi bir ixtiyoriy element turiga ega ustuvor navbat strukturasini qaytarishi mumkin. Endi, agar bizga satr ustuvor navbati va butun son ustuvorligi kerak bo'lsa navbat, biz yozishimiz mumkin : functor RootedSkewBinomialQueue = AddRootToFun (functor MakeQ = SkewBinomialQueue) 23 structure StringQueue = RootedSkewBinomialQueue (StringElem) structure IntQueue = RootedSkewBinomialQueue (IntElem) bu erda StringElem va IntElem ORDERED imzosiga mos keladi va mos ravishda satrlar va butun sonlar bo'yicha kerakli tartiblarni aniqlaydi. 3.2. Bootstrapping ustuvor navbatlar . Nihoyat, a ni qo'llash orqali eritmaning ishlash vaqtini O(1) ga yaxshilaymiz. Buchsbaum va boshqalarning texnikasi. (Buchsbaum va boshqalar, 1995; Buchsbaum & Tarjan, 1995) ma'lumotlar-strukturali yuklash deb ataladi. Asosiy fikr deb ustuvor navbatlar yordamida oddiy kiritish uchun eritish kamaytirish hisoblanadi. Boshqa ustuvor navbatlarni o'z ichiga oladi. Keyin, ikkita ustuvor navbatni birlashtirish uchun biz shunchaki bir ustuvor navbatni ikkinchisiga qo'ying. Oldingi bo'limda bo'lgani kabi, biz yuklashni ustuvor navbatlarda modul darajasidagi transformatsiya sifatida tasvirlaymiz. P a ibtidoiyning turi bo'lsin a tipidagi elementlarni o'z ichiga olgan ustuvor navbatlar. Biz elementlarini o'z ichiga olgan yuklangan ustuvor navbatlarning BP a turi a turini qurishni xohlaymiz. Yuklangan ustuvor navbat ibtidoiy ustuvorlik "elementlari" boshqa yuklangan ustuvor navbatlar bo'lgan navbat kabi bo'ladi. Birinchi urinish, biz ko'rib chiqamiz : BP a = PP a (2) Bu erda biz yuklashning yagona darajasini qo'lladik. Biroq, bu oddiy yechim ishlamaydi, chunki yuqori darajadagi elementlar ibtidoiy ustuvor navbat noto'g'ri turga ega - ular yuklangan ustuvor navbatlardan ko'ra oddiy ibtidoiy ustuvor navbatlardir. Aniq, bootstrapping g'oyasini rekursiv ravishda qo'llashimiz kerak, masalan BP a = P bp a (3) Afsuski, bu yechim oddiy elementlarni saqlash uchun joy taklif qilmaydi. 24 Shuning uchun biz oldingi bo'limdan qarz olamiz va har biriga ildiz qo'shamiz ibtidoiy ustuvor navbat. BP a = a × P bp a (4) Shunday qilib, yuklangan ustuvor navbat oddiy elementdir (bu kerak navbatdagi minimal element bo'lsin) primitiv ustuvorlik bilan bog'langan. Ular tomonidan buyurtma qilingan boshqa yuklangan ustuvor navbatlarni o'z ichiga olgan navbat tegishli minimumlar. Bootstrapping har bir ibtidoiy ustuvor navbatga ildiz qo'shganligi sababli, bootstrapping transformatsiyasi o'z ichiga oladi. AddRoot transformatsiyasi. Nihoyat, biz imkoniyatga ruxsat berishimiz kerak bo'sh navbat. Yakuniy ta'rif shunday BP a = {bo'sh} + R a bu erda R a = a × P R a (5) E'tibor bering, ibtidoiy ustuvor navbatlar element sifatida faqat bo'sh bo'lmagan yuklangan ustuvor navbatlarni o'z ichiga oladi. Endi yuklangan ustuvor navbatlardagi operatsiyalarning har biri bo'lishi mumkin. Ibtidoiy ustuvor navbatlar bo'yicha operatsiyalar nuqtai nazaridan aniqlanadi. Uchun ustuvor navbatlardagi har bir f operatsiyasi f va f0 operatsiyalarni bildirsin mos ravishda PR a va BP a bo'yicha. Keyin, findMin0 (hx, qi) = x insert0 (x, q) = meld0 (hx, emptyi, q) meld0 (hx1, q1i,hx2, q2i) = hx1, insert (hx2, q2i, q1)i if x1 ≤ x2 meld0 (hx1, q1i,hx2, q2i) = hx2, insert (hx1, q1i, q2)i if x2 < x1 deleteMin0 (hx, qi) = hy, meld(q1, q2)i where hy,q1i = findMin (q) q2 = deleteMin (q) Keyinchalik, yuklangan ustuvor navbatlarning samaradorligini ko'rib chiqamiz. Minimal element ildizda saqlanganligi sababli findMin O(1) ni talab qiladi. Asosiy amalga oshirishdan qat'iy nazar vaqt qo'shish va birlashtirish operatsiyalar 25 faqat ibtidoiy amalga oshirishning kiritilishiga bog'liq. Egrilik kabi O(1) kiritish bilan ustuvor navbatni yuklash orqali binomial navbatlar, biz O (1) kiritish va O (1) ni olamiz. Nihoyat, yuklangan ustuvor navbatlarda deleteMin bog'liq findMin- da, asosiy dasturdan birlashtiring va deleteMin-ni tanlang. Egri binomial navbatlar O (log n) vaqtida ularning har birini qo'llab-quvvatlaganligi sababli, Bootstrapped skew binomial navbatlardagi deleteMin ham O(log n) ni talab qiladi. Lekin, hech qanday taqqoslashga asoslangan ustuvor navbat qo'shishni yaxshiroq qo'llab- quvvatlay olmaydi. O(log n) eng yomon holat vaqti yoki O(n) eng yomon holat vaqtidan yaxshiroq aralashish findMin yoki deleteMin dan biri kamida O(log n) eng yomon holatni qabul qilmasa vaqt (Brodal, 1995). Yuklash jarayoni standartda oqlangan tarzda ifodalanishi mumkin. ML yuqori tartibli funktorlar va rekursiv tuzilmalar bilan kengaytirilgan, kabidir. Bootstrap ning yuqori tartibli tabiati o'xshashdir. AddRootToFun ning yuqori tartibli tabiatiga, RootedQ va Q o'rtasidagi rekursiya esa Ra va PRa o'rtasidagi rekursiyani ushlaydi. Afsuski, Standard ML ning ba'zi ilovalari qo'llab-quvvatlansa ham yuqori tartibli funktorlar (MacQueen & Tofte, 1994), hech biri rekursiv tuzilmalarni qo'llab-quvvatlamaydi, shuning uchun RootedQ va Q o'rtasidagi rekursiya taqiqlanadi. Aslida, bu kabi rekursiyani qo'llab-quvvatlamaslik uchun yaxshi sabablar bor umumiy. Misol uchun, agar MakeQ bo'lsa, bu rekursiya hatto mantiqiy bo'lmasligi mumkin hisoblash effektlari bo'lishi mumkin! Biroq, SkewBinomialQueue kabi ko'plab ustuvor navbat funksiyalari shunchaki bir nechta ma'lumotlar turlarini belgilaydi va funktsiyalari va hisoblash effektlariga ega emas. Bu yaxshi xulqlilar uchun Funktorlar uchun RootedQ va Q o'rtasidagi rekursiya mantiqiy ko'rinadi va bu funktorlarni yuklash yoqimli bo'lardi. shu tarzda. Xulosa qilib aytganda, yuklangan skew binomial navbatlar O(1) vaqtidagi har bir amalni qo llab-quvvatlaydi, bu O(log n) vaqtini talab qiladiganʻ deleteMindan tashqari. Bu chegaralar barcha taqqoslashga asoslangan ustuvor navbatlar orasida optimal ekanligini tartiblashni qisqartirish orqali ko'rsatish oson. 26 Turli operatsiyalarning ishlash vaqtlari o'rtasidagi boshqa kelishuvlar ham mumkin. Rekursiv tuzilmalarsiz biz hali ham bootstrapped-ni amalga oshirishimiz mumkin. Ustuvor navbatlar, lekin juda kamroq toza. MakeQ uchun tegishli ustuvor navbat funksiyasini kiritib, Q va RootedQ-ni yo'q qilish orqali Bootstrap-ni istalgan ibtidoiy ustuvor navbatga qo'lda ixtisoslashtiramiz. Alohida tuzilmalar sifatida. Bu standart ML tomonidan osonlik bilan qo'llab-quvvatlanadigan ma'lumotlar turlari bo'yicha rekursiyaga tuzilmalardagi rekursiyani kamaytiradi. Albatta, har qanday qo'lda dasturni o'zgartirish kabi, bu jarayon zerikarli va xatoga moyil. functor Bootstrap (functor MakeQ (E : ORDERED) : sig include PRIORITY QUEUE sharing Elem = E end) (E : ORDERED) : PRIORITY QUEUE = struct structure Elem = E ( ∗ recursive structures not supported in SML! ∗ ) structure rec RootedQ = struct datatype T = Root of Elem.T × Q.T fun leq (Root (x1, q1), Root (x2, q2)) = Elem.leq (x1, x2) end and Q = MakeQ (RootedQ) open RootedQ ( ∗ expose Root constructor ∗ ) datatype T = Empty | NonEmpty of RootedQ.T val empty = Empty fun isEmpty Empty = true 27 | isEmpty (NonEmpty ) = false fun insert (x, xs) = meld (NonEmpty (Root (x, Q.empty)), xs) and meld (Empty, xs) = xs | meld (xs, Empty) = xs | meld (NonEmpty (r1 as Root (x1, q1)), NonEmpty (r2 as Root (x2, q2))) = if Elem.leq (x1, x2) then NonEmpty (Root (x1, Q.insert (r2, q1))) else NonEmpty (Root (x2, Q.insert (r1, q2))) exception EMPTY fun findMin Empty = raise EMPTY | findMin (NonEmpty (Root (x, q))) = x fun deleteMin Empty = raise EMPTY | deleteMin (NonEmpty (Root (x, q))) = if Q.isEmpty q then Empty else let val (Root (y, q1)) = Q.findMin q val q2 = Q.deleteMin q in NonEmpty (Root (y, Q.meld (q1, q2))) end end 3.3. Optimallashtirish . Oldingi bo'limda tasvirlangan yuklangan egilgan binomial navbatlar asimptotik jihatdan optimal bo'lsa-da, biz hali ham qo'shimcha optimallashtirishlarni amalga oshirishimiz mumkin. Natijada paydo bo'ladigan ustuvor navbatlar turini ko'rib chiqing. MakeQ uchun SkewBinomialQueue qatoridan: Datatype Tree = Ildiz tugun × Rank × Daraxt ro'yxati va Root = Root of Elem.T × Tree ro'yxati ma'lumotlar turi T = Bo'sh | Ildiz bo'sh emas Ushbu tasvirda tugun Node(Root(x, f), r, c) ko'rinishiga ega, bu erda x - element, f - o'rmonni ifodalovchi daraxtlar ro'yxati, r - daraja va c - tugunning bolalarini 28 ifodalovchi daraxtlar ro'yxati. Har yili tugun x va f ni o'z ichiga oladi, biz tugunlarning tasvirini tekislashimiz mumkin. datatype Tree = Elem.T tugunlari × Daraxtlar ro'yxati × Rank × Daraxtlar ro'yxati. Ko'pgina ilovalarda bu har birida bilvositalikni yo'q qiladi x ga kirish. Keyinchalik, f ildizi o'chirilmaguncha butunlay e'tiborga olinmasligini unutmang. Shunday qilib, biz f ga to'g'ridan-to'g'ri kirishni talab qilmaymiz va uni aslida saqlashimiz mumkin. c ning dumi, ikkalasini c ++ f ni ifodalovchi yagona ro'yxatga birlashtiradi. Bu odatda so'zni saqlaydigan quyidagi vakillikka olib keladi. Har bir tugunda saqlash: Datatype Tree = Elem.T tugunlari × Rank × Daraxtlar ro'yxati Ushbu ko'rinishda deleteMin davomida c ni kesib o'tish kerak. f ga kirish uchun, lekin biz 0 darajasini olish uchun baribir c orqali o'tishimiz kerak bolalar va qolgan bolalarni teskari aylantiring. r darajali tugun berilgan, c qayerda tugaydi va f qaerda boshlanadi aniqlash odatda juda oson. Agar r = 0 bo'lsa, keyin c = [ ]. Agar r = 1 bo'lsa, u holda c bitta yoki ikkita 0 darajasidan iborat tugunlar. Agar r > 1 bo'lsa, u holda c bir xil juft tugunlar bilan tugaydi nolga teng bo'lmagan daraja yoki 1-darajali tugun, undan keyin bir yoki ikkita darajali 0 tugunlari. Faqatgina noaniqliklar 0-darajali tugunlarni o'z ichiga oladi: ba'zida bu mumkin emas. c dan ikkita darajali 0 tugunlari bilan tugaydigan holatni ajratish uchun c bitta darajali 0 tugun bilan tugaydigan va f daraja bilan boshlanadigan holat 0 tugun. Biroq, har bir bunday vaziyatda, uni davolash hech qanday zarar qilmaydi noaniq tugun, xuddi f emas, c ning bir qismi. Yakuniy soddalashtirish sifatida, daraxtlar va orasidagi farqni unutmang ildizlar kerak emas, chunki har bir ildizni darajali daraxt sifatida ko'rish mumkin Bizning yakuniy vakilimiz keyin datatype Tree = Elem.T tugunlari × Rank × Daraxtlar ro'yxati ma'lumotlar turi T = Bo'sh | NonEmpty of Tree 29 Bu har bir ildizning hajmini biroz oshiradi, lekin ba'zilarini ham yo'q qiladi melds paytida kichik nusxa ko'chirish. 4. Tegishli ish va muhokama Imperativ ustuvor navbatlar bo'yicha juda ko'p adabiyot mavjud bo'lsa-da, sof funktsional ustuvor navbatlar ustida juda kam ish olib borildi. Paulson (1991) birlashtirish (birlashtirib bo'lmaydigan) ustuvor navbatni tasvirlaydi an'anaviy ravishda yashirin yig'ish texnikasi (Williams, 1964) ning muvozanatli daraxt tasviri bilan massivlar yordamida amalga oshiriladi. Orqa tomonda kengaytmani qo'llab-quvvatlovchi massivlar. Hoogerwoord (1992) Paulson kabi daraxtlardan foydalangan holda massivlarni ifodalaydi, lekin massivlarga ham ruxsat beradi. old tomondan uzaytirilishi kerak. dan foydalangan holda Paulson navbatlarining bir varianti Hoogerwoord-ning biroz sodda oldingi kengaytmasi uning bir qismi bo'lib funktsional folklor dasturlash ko'rinadi. King (1994) binomialning sof funktsional navbatlar amalga oshirilishini taqdim etadi. Garchi binomial navbatlar imperativ sharoitlarda ancha murakkab hisoblansa ham (Jones, 1986), King shuni ko'rsatadiki, funktsional tillarning ro'yxatini qayta ishlashning qulayroq imkoniyatlari binomial navbatlarni juda oqlangan tarzda qo'llab-quvvatlang. Schoenmakers (1992), Kaldewaij bilan oldingi ishlarni kengaytirdi (1991), 30 amortizatsiyalangan chegaralarni chiqarishda yordam berish uchun funktsional belgilardan foydalanadi. Bir qator ma'lumotlar tuzilmalari uchun, jumladan, uchta ustuvor navbat: skew heaps1 (Sleator & Tarjan, 1986), Fibonachchi heaps (Fredman & Tarjan, 1987) va juftlash to'plari (Fredman va boshq., 1986). Schoenmakers ham yassi daraxtlarni muhokama qiladi (Sleator va Tarjan, 1985), Jones (1986) tomonidan eshilmaydigan ustuvor navbat sifatida ayniqsa samarali ekanligi ko'rsatilgan o'z-o'zidan sozlanadigan ikkilik qidiruv daraxtining shakli. Ushbu to'rtta ma'lumotlarning har biri tuzilmalar faqat amortizatsiyalangan ma'noda samarali bo'ladi. U ishlatsa ham funktsional nota, Schoenmakers uning e'tiborini vaqtinchalik bilan cheklaydi. Ma'lumotlar tuzilmalaridan foydalanish, bu erda faqat ma'lumotlarning eng so'nggi versiyasi strukturaga kirish yoki yangilash mumkin. Efemerlik chambarchas bog'liq chiziqlilik tushunchasiga (Wadler, 1990). Qat'iylikka ruxsat berilganda, An'anaviy amortizatsiya qilingan tahlillar buziladi, chunki ma'lumotlar strukturasining "qimmat" versiyalari bo'yicha operatsiyalar o'zboshimchalik bilan tez-tez takrorlanishi mumkin. Okasaki (1995a; 1996) yashirin yodlashdan qanday foydalanishni tasvirlaydi chegaralari amortizatsiya qilingan ma'lumotlar tuzilmalarini qo'llab-quvvatlash uchun dangasa baholashda qat'iylik ostida ham ushlab turing. Biroq, yuqoridagi ma'lumotlar tuzilmalaridan, Bu texnikaga faqat juftlik uyumlari mos keladi. Va nihoyat, bizning ma'lumotlar tuzilmasi bir nechta manbalardan texnikani oladi. Skew linking Okasaki tasodifiy kirish ro'yxatidan olingan (1995b), bu esa o'z navbatida tasodifiy kirish steklarining modifikatsiyasi hisoblanadi Myers (1983). Qo'shish narxini kamaytirish uchun biz egilgan bog'lanishdan foydalanamiz O (1) ga binomial navbatlarda, lekin rekursiv sekinlashuv (Kaplan va Tarjan, 1995) va dangasa baholash (Okasaki, 1996) uchun ishlatilishi mumkin. bir xil maqsad. Ma'lumotlar strukturaviy yuklash Buchsbaum tomonidan qo'llaniladi va boshqalar. (Buchsbaum va boshq., 1995; Buchsbaum va Tarjan, 1995) ikki tomonlama navbatlar uchun katenatsiyani ustuvor navbatlar uchunni qo'llab-quvvatlash uchun, xuddi biz uni qo'llab-quvvatlash uchun ishlatamiz. 31 4.1. Munozara . Biz O(1) eng yomon holatda findMinni qo'llab-quvvatlash, kiritish va birlashtirish uchun ustuvor navbatlarning birinchi sof funktsional bajarilishini tasvirlab berdik. Vaqt, va O(log n) eng yomon holatda deleteMin. Bu chegaralar taqqoslashga asoslangan barcha ustuvor navbatlar orasida asimptotik optimal. Bizning ma'lumotlar tuzilmasi imperativ ma'lumotlar strukturasini moslashtirishdir Brodal (1995) tomonidan kiritilgan, lekin biz ikkalamiz ham uning asl nusxasini soddalashtirdik. Ma'lumotlar tuzilishi va uning binomial navbatlari bilan bog'liqligini aniqladi Vuillemin (1978). Bizning ma'lumotlar tuzilmamiz amalda juda samarali; Ammo, bir necha raqobat ma'lumotlar tuzilmalari bor, garchi asimptotik jihatdan optimal emas, amalda biznikidan biroz tezroq. Demak, bizning ishimiz birinchi navbatda nazariy qiziqish uyg'otadi. Asosiy hudud unda bizning ma'lumotlar tuzilmasi amalda foydali bo'lishi kerak bo'lgan ilovalar qotishma ustunlik qiladi, ayniqsa doimiy ustuvor navbatlarni talab qiladigan ilovalar. Biz standart ML-da ma'lumotlar tuzilmamizni amalga oshirgan bo'lsak-da, a qat'iy funktsional til, uni boshqa funktsional tillarga, hatto Xaskell kabi dangasa tillarga osongina tarjima qilish mumkin edi (Hudak va boshqalar, 1992). Biroq, dangasa tilda, eng yomon chegaralar bo'ladi. Amortizatsiya qilinadi, chunki har bir qo'shish, birlashtirish va o'chirishMin amallari ularning natijalari findMin tomonidan kerak bo'lguncha kechiktiriladi. Masalan, a m kiritish va birikmalar ketma-ketligidan keyin findMin Ō(m) oladi. Vaqt, garchi bu vaqt qo'shimchalar bo'yicha amortizatsiya qilinishi mumkin va odatiy tarzda aralashadi. Bu muammo bizning ma'lumotlar tuzilmamizga xos emas - bu deyarli barcha nominal ma'lumotlar tuzilmalariga tegishli dangasa tilda. To'liqroq muhokama qilish uchun Okasaki (1995a; 1996) ga qarang dangasa baholash va amortizatsiya o'rtasidagi o'zaro ta'sir. Keyinchalik, imperativ ustuvorlik navbatlari ko'pincha ikkita qo'shimcha operatsiyani qo'llab-quvvatlashini ta'kidlaymiz, bu kamaytirish va o'chirish tugmachalari va o'chirish navbatning belgilangan elementi. Ko'rib chiqilayotgan 32 element odatda navbatning o'rtasiga ko'rsatgich bilan belgilanadi, lekin bu funktsional sharoitda noqulay. Bir yondashuvni ifodalashdir navbatni ikkilik qidiruv daraxti sifatida qo'ying, shuning uchun biz ixtiyoriy elementlarni samarali qidirishimiz mumkin. Bu, asosan, King (1994) tomonidan qabul qilingan yondashuv. Jons (1986) tomonidan ampirik taqqoslashlar, yassi daraxtlar bo'lishini ko'rsatadi bu maqsad uchun ideal bo'l, hech bo'lmaganda asosan vaqtinchalik foydalanish uchun. Afsuski, ikkilik qidiruv daraxtlarini (jumladan, chayqalish daraxtlarini) birlashtirish O(n) vaqtini talab qiladi. Muqobil yondashuv - ikkita ustuvor navbatdan foydalanish, biri elementlarning "ijobiy" hodisalarini va ikkinchisi "salbiy" ni o'z ichiga olgan elementlarning paydo bo'lishi. Elementni o chirish uchun uni ichiga kiritish kifoyaʻ salbiy navbat. Elementni kamaytirish uchun eski qiymatni o'chiring va yangi qiymatni kiriting. Xuddi shunday ijobiy va salbiy hodisalar element ikkalasi ham minimal bo'lganda bir-birini bekor qiladi ularning tegishli navbatlari elementlari. Ushbu yondashuvni Tarjan (1983) dangasa o'chirish operatsiyasining funktsional analogi sifatida ko'rish mumkin. Salbiy elementlar soni bo'lsa, bu yechim yaxshi ishlaydi nisbatan kichik. Biroq, ko'p ijobiy-salbiy juftliklar mavjud bo'lganda hali bir-birini bekor qilmagan, bu yechim ham vaqt, ham makonda samarasiz bo'lishi mumkin. Qo'llab-quvvatlash uchun qo'shimcha tadqiqotlar talab qilinadi kamaytirishKey va funktsional sozlamada samarali o'chirish. Kelajakdagi ishning yakuniy sohasi standart ML modul tizimiga tegishli. Rekursiv modullar har doim ham mantiqiy emas, va shuning uchun hozirda tilni amalga oshirishda taqiqlangan. Biroq, modul darajasida rekursiya oqilona ko'rinadi va foydali ba'zi yaxshi ishlaydigan modullar uchun. Bu qiziq bo'lardi rekursiv modullar bo'lishi kerak bo'lgan shartlarni rasmiylashtirish ruxsat etiladi va shunga mos ravishda Standard ML ning ba'zi joriy etilishini kengaytiradi. 33 XULOSA Men “ Brodala – Okasaki uyumi “ mavzusidagi algoritm g’oyasini yanada mukamalroq o’rgandim. Brodal - Okasaki kaskadli havolalarsiz binomial qoziqdan foydalanish, minimal element qo'shish va ma'lumotlar strukturasini yuklash g'oyasiga asoslanganligini bilib oldim. Sof funktsional ma'lumotlar tuzilmalari imperativ ma'lumotlar tuzilmalaridan kamida ikki jihatdan farq qilar ekan. Birinchidan, ko'plab imperativ ma'lumotlar tuzilmalari samaradorlik uchun halokatli topshiriqlarga tayanadi, holbuki sof funktsional ma'lumotlar tuzilmalariga halokatli topshiriqlardan foydalanish taqiqlanadi. Ikkinchidan, sof funktsional ma'lumotlar tuzilmalari avtomatik ravishda doimiy ya'ni yangilanishdan keyin ikkalasi ham ma'lumotlar strukturasining yangi va eski versiyalari keyingi ma'lumotlar uchun mavjud kirish va yangilanishlardir. Bundan farqli o'laroq, imperativ ma'lumotlar tuzilmalari deyarli har doim vaqtinchalik bo'lar ekan, ya'ni yangilanishdan keyin faqat yangi ma'lumotlar strukturasi versiyasi mavjud. Ko'pgina hollarda, algoritm matnlarida tasvirlanganlar kabi ma'lumotlar tuzilmalari funktsional dasturchilarga oddiygina foydalanishga to'sqinlik qiladi. Shunday qilib, samarali sof funktsional ma'lumotlar tuzilmalarini loyihalash katta ahamiyatga ega. Funktsional dasturchilar uchun nazariy va amaliy qiziqish, shuningdek doimiy 34 bo'lgan holatlar uchun imperativ dasturchilarga kelsak ma'lumotlar tuzilishi talab qilinar ekan. FOYDALANILGAN ADABIYOTLAR Brodal, Gert Stolting. (1995). Tez eriydigan ustuvor navbatlar. 282–290 sahifalar: Algoritmlar va ma'lumotlar tuzilmalari bo'yicha seminar. LNCS, jild. 955. Springer-Verlag. Brodal, Gert Stolting. 1996 yil (yanvar). Eng yomon holatda ustuvor navbatlar. 52–58 sahifalar: Diskret algoritmlar bo'yicha ACM-SIAM simpoziumi. Braun, Mark R. (1978). Binomli navbat algoritmlarini amalga oshirish va tahlil qilish. SIAM Journal on Computing, 7(3), 298–319. Buchsbaum, Adam L. va Tarjan, Robert E. (1995). Confluently persistent deques via ma'lumotlarni tizimli yuklash. Algoritmlar jurnali, 18(3), 513–547. Buchsbaum, Adam L., Sundar, Rajamani va Tarjan, Robert E. (1995). Ma'lumotlar-strukturaviy yuklash, chiziqli yo'lni siqish va katenable yig'ma-tartibli ikki tomonlama navbatlar. SIAM Journal on Computing, 24(6), 1190–1206. 35 Kreyn, Klark Allan. 1972 yil (fevral). Balanslangan ikkilik sifatida chiziqli ro'yxatlar va ustuvor navbatlar daraxtlar. Ph.D. dissertatsiya, Stenford universiteti kompyuter fanlari bo'limi. Mavjud STAN-CS-72-259 sifatida Driscoll, Jeyms R., Sarnak, Neil, Sleator, Daniel D. K. va Tarjan, Robert E. (1989). Ma'lumotlar tuzilmalarini barqaror qilish. Kompyuter va tizim fanlari jurnali, 38(1), 86–124. Fredman, Maykl L. va Tarjan, Robert E. (1987). Fibonachchi to'plari va ulardan foydalanish takomillashtirilgan tarmoqni optimallashtirish algoritmlari. ACM jurnali, 34(3), 596–615. Fredman, Maykl L., Sedgewick, Robert, Sleator, Daniel D. K. va Tarjan, Robert E. (1986). Juftlik uyasi: o'z-o'zidan sozlanadigan to'pning yangi shakli. Algoritmik, 1(1), 111–129. Hud, Robert. 1982 yil (avgust). Juda yuqori darajadagi dasturlash tili konstruksiyalarini samarali amalga oshirish. Ph.D. dissertatsiya, kompyuter fanlari kafedrasi, Kornell universiteti. (Cornell TR 82-503). Hugervurd, Rob R. (1992). Moslashuvchan massivlarning logarifmik bajarilishi. Sahifalar 191–207: Dasturni qurish matematikasi bo'yicha konferentsiya. LNCS, jild. 669. Springer-Verlag. Hudak, Pol, Peyton Jons, Saymon, Uodler, Filipp, Boutel, Brayan, Fairbairn, Jon, Fasel, Jozef, Guzman, Marya M., Hammond, Kevin, Xyuz, Jon, Jonson, Tomas, Kiburts, Dik, Nikhil, Rishiyur, Partain, Uill va Peterson, Jon. (1992). Haskell funktsional dasturlash tili bo'yicha hisobot, 1.2-versiya. SIGPLAN 36 Eslatmalar, 27(5). Jons, Duglas V. (1986). Ustuvorlik navbati va voqealar to'plamini empirik taqqoslash amalga oshirishlar. ACM kommunikatsiyalari, 29(4), 300–311. Kaldewaij, Anne va Schoenmakers, Berry. (1991). Qattiqroq chegaraning kelib chiqishi yuqoridan pastga egilgan uyumlar uchun. Axborotni qayta ishlash xatlari, 37(5), 265–271. Kaplan, Xaim va Tarjan, Robert E. 1995 (may). Katenatsiya orqali doimiy ro'yxatlar rekursiv sekinlashuv. 93–102 sahifalar: Hisoblash nazariyasi bo'yicha ACM simpoziumi. King, Devid J. 1994 (sentyabr). Funktsional binomial navbatlar. 141–150 sahifalar: Glasgow Funktsional dasturlash bo'yicha seminar. MakQuin, Devid B. va Tofte, Mads. 1994 yil (aprel). Yuqori tartibli funktorlar uchun semantika. 409–423 sahifalar: Dasturlash bo'yicha Yevropa simpoziumi. Milner, Robin, Tofte, Mads va Harper, Robert. (1990). Standartning ta'rifi ML. Kembrij, Massachusets: MIT matbuoti. Myers, Eugene W. (1983). Amaliy tasodifiy kirish stek. Axborotni qayta ishlash Xatlar, 17(5), 241–248. Okasaki, Kris. 1995a (oktabr). Amortizatsiya, dangasa baholash va qat'iyatlilik: Ro'yxatlar dangasa bog'lanish orqali katenatsiya bilan. 646–654 sahifalar: Kompyuter fanlari asoslari bo yicha IEEE simpoziumi.ʻ Okasaki, Kris. 1995 yil (iyun). Sof funktsional tasodifiy kirish ro'yxatlari. 86–95 sahifalar: Funktsional dasturlash tillari va kompyuter arxitekturasi konferensiyasi. Okasaki, Kris. (1995c). Oddiy va samarali sof funktsional navbatlar va deklar. 37 Funktsional dasturlash jurnali, 5(4), 583–592. Okasaki, Kris. 1996 yil (may). Amortizatsiyalangan ma'lumotlar tuzilmalarida dangasa baholashning roli. 62–72 sahifalar: Funktsional dasturlash bo'yicha ACM SIGPLAN xalqaro konferentsiyasi. Paulson, Lorens C. (1991). Ishchi dasturchi uchun ML. Kembrij: Kembrij universiteti nashriyoti. Schoenmakers, Berri. 1992 yil (sentyabr). Ma'lumotlar tuzilmalari va amortizatsiya qilingan murakkablik a Funktsional sozlash. Ph.D. dissertatsiya, Eyndxoven Texnologiya Universiteti. Sleator, Daniel D. K. va Tarjan, Robert E. (1985). O'z-o'zidan sozlanadigan ikkilik qidiruv daraxtlari. ACM jurnali, 32(3), 652–686. Sleator, Daniel D. K. va Tarjan, Robert E. (1986). O'z-o'zidan sozlanadigan to'plar. SIAM jurnali Hisoblash bo'yicha, 15(1), 52–69. Tarjan, Robert E. (1983). Ma'lumotlar tuzilmalari va tarmoq algoritmlari. Mintaqaviy CBMS Amaliy matematika bo'yicha konferentsiyalar seriyasi, jild. 44. Filadelfiya: Sanoat va amaliy matematika jamiyati. Vuillemin, Jan. (1978). Ustuvor navbatlarni manipulyatsiya qilish uchun ma'lumotlar strukturasi. ACM kommunikatsiyalari, 21(4), 309–315. Uodler, Filipp. 1990 yil (aprel). Chiziqli turlar dunyoni o'zgartirishi mumkin! 561– 581 sahifalar: Dasturlash kontseptsiyalari bo'yicha IFIP TC 2 ishchi konferentsiyasi materiallari va Usullari. Uilyams, J. V. J. (1964). 232-algoritm: Ustma-sort. ACM kommunikatsiyalari, 7(6), 347–348. 38 39

Brodala – Okasaki uyumi MUNDARIJA: KIRISH …………………………………………………………………………… 3 1. Brodal va Okasakining ustuvor navbati ……………………………………… 5 1.1 Eng qiyin operatsiya deleteMin ……………………………………………… 6 1.2. Brodalning ma'lumotlar strukturasi ………………………………………...9 2. Ikkilamchi navbatlar ………… … …………………… … …… … …… ……… 12 3. Global ildiz qo'shish … ……………………………… … ………… ………… 20 3.1. AddRoot optimallashtirish … ……………………………… … ………… ... 22 3.2. Bootstrapping ustuvor navbatlar … ……………………………… … ……24 3.3. Optimallashtirish … …… … …… … ……………………………… … ……..28 4. Tegishli ish va muhokama ……… … …… … …… … ………………………… 30 4.1. Munozara ……… … …… …… …… …… ……… … ………………………… 31 XULOSA ……………………………………………………………………….... 34 FOYDALANILGAN ADABIYOTLAR ……………………………………… 35 1

Kirish Brodal Okasaki (ingl. Brodal's and Okasaki's Priority Queue)-kaskadli havolalarsiz binomial qoziqdan foydalanish, minimal element qo'shish va ma'lumotlar strukturasini yuklash g'oyasiga asoslangan. Birinchisi sizga imkon beradi insert uchun O(1), ikkinchisi sizga minimal elementni olish imkonini beradi O(1), uchinchisi esa bajarishga imkon beradi merge uchun O(1). Minimalni olib tashlash quyidagilar uchun ishlaydi O(logN) eng yomon holatda. Ushbu hisob- kitoblar taqqoslashga asoslangan barcha ustuvor navbatlar orasida asimptotik jihatdan maqbuldir. Bu chegaralar asimptotikdir barcha taqqoslashga asoslangan ustuvor navbatlar orasida optimal. Brodalning ma'lumotlar strukturasi sof funktsional sozlamalarga ega. Bunda Vuillemin ma'lumotlar strukturasini soddalashtirish va uning binomial navbatlar bilan aloqasini aniqlashtirish O(log n) vaqtida barcha to'rtta operatsiyani qo'llab-quvvatlaydi. Xususan, biz amalga oshirishni binomial navbatlardan uch bosqichda olamiz: birinchidan, biz kaskadli havolalar imkoniyatidan foydalanib, qo'shimchaning ishlash vaqtini O(1) ga qisqartiramiz; ikkinchidan, minimal elementni ushlab turish uchun global ildiz qo'shish orqali findMin ning ishlash vaqtini O(1) ga qisqartiramiz; va nihoyat, ustuvor navbatlar boshqasini o'z ichiga olishiga ruxsat berish orqali qotishning ishlash vaqti O(1) ga kamaytiramiz. Ushbu bosqichlarning har biri ML uslubidagi funktorlar yordamida ifodalanadi. Ma'lumotlar-strukturali yuklash deb nomlanuvchi so'nggi 2

transformatsiya qiziqarli yuqori tartibli funktorlar va rekursiv tuzilmalarni qo'llashdir. Sof funktsional ma'lumotlar tuzilmalari imperativ ma'lumotlar tuzilmalaridan kamida ikki jihatdan farq qiladi. Birinchidan, ko'plab imperativ ma'lumotlar tuzilmalari samaradorlik uchun halokatli topshiriqlarga tayanadi, holbuki sof funktsional ma'lumotlar tuzilmalariga halokatli topshiriqlardan foydalanish taqiqlanadi. Ikkinchidan, sof funktsional ma'lumotlar tuzilmalari avtomatik ravishda doimiy ya'ni yangilanishdan keyin ikkalasi ham ma'lumotlar strukturasining yangi va eski versiyalari keyingi ma'lumotlar uchun mavjud kirish va yangilanishlardir. Bundan farqli o'laroq, imperativ ma'lumotlar tuzilmalari deyarli har doim vaqtinchalik bo'ladi, ya'ni yangilanishdan keyin faqat yangi ma'lumotlar strukturasi versiyasi mavjud. Ko'pgina hollarda, algoritm matnlarida tasvirlanganlar kabi ma'lumotlar tuzilmalari funktsional dasturchilarga oddiygina foydalanishga to'sqinlik qiladi. Shunday qilib, samarali sof funktsional ma'lumotlar tuzilmalarini loyihalash katta ahamiyatga ega. Funktsional dasturchilar uchun nazariy va amaliy qiziqish, shuningdek doimiy bo'lgan holatlar uchun imperativ dasturchilarga kelsak ma'lumotlar tuzilishi talab qilinadi. Ustuvor navbat kompyuter dasturlashda asosiy abstraksiyadir, faqat lug'at orqali muhimligi oshib ketgan ketma-ketlik. Ustuvor navbatlarning ko'plab tatbiqlari amalga oshirilishi yillar davomida taklif qilingan, kichik namuna : (Williams, 1964; Kran, 1972; Vuillemin, 1978; Fredman va Tarjan, 1987; Brodal, 1996). Biroq, bularning barchasi faqat imperativ ustuvor navbatlarni hisobga oladi. Juda sof funktsional ustuvor navbatlar haqida kam yozilgan. Bizning bilim, faqat Paulson (1991), Kaldewaij va Schoenmakers (1991), Schoenmakers (1992) va King (1994) ustuvorliklarga aniq munosabatda bo'lishdi. 3

1. Brodal va Okasakining ustuvor navbati Binomli navbatlar ustuvor navbatning nafis shaklidir. Vuillemin (1978) va Braun (1978) tomonidan keng o'rganilgan. Garchi ular binomial navbatlarni faqat imperativ sharoitda ko'rib chiqqan bo’lsalar ham, King (1994) binomial navbatlar funktsional sharoitda teng darajada yaxshi ishlashini ko'rsatdi. Ushbu bo'limda biz binomial navbatlarni qisqacha ko'rib chiqamiz . Binomli navbatlar ibtidoiy deb nomlanuvchi ob'ektlardan iborat binomial daraxtlar. Binom daraxtlari induktiv ravishda quyidagicha aniqlanadi: • 0-darajali binom daraxti yagona tugundir. • r+1 darajali binom daraxti ikkita binomni bog‘lash orqali hosil bo‘ladi. r-darajali daraxtlar, bir daraxtni ikkinchisining eng chap bolasi qilib oladi. Ushbu ta'rifdan r darajali binomial daraxt ekanligini ko'rish oson aniq 2r tugunni o'z ichiga oladi. Ikkinchi, ekvivalent ta'rifi. Ba'zan qulayroq bo'lgan binomial daraxtlar: binomial daraxt r rank - r bolalar t1 ...tr bo'lgan tugun, bu erda har bir ti binomdir r - i darajali daraxt. Tugunlar bo'yicha umumiy tartibni nazarda tutsak, binomial daraxt deyiladi har bir tugun ≤ har bir avlodi bo'lsa, yig'ma tartibli. Saqlash uchun Ikki uyin tartibli daraxtlarni bog'lashda yig'ish tartibini qilamiz ildizi kattaroq daraxt - kichikroq ildizli daraxtning bolasi, bilan aloqalar o'zboshimchalik bilan uziladi. 4

Bir binomial binomial navbat, bu erda yig'ilgan tartibli binomial daraxtlar o'rmonidir ikkita daraxt bir xil darajaga ega emas. Chunki binomial daraxtlarning o'lchamlari bor 2 r shakldagi, n o'lchamdagi binomial navbatdagi daraxtlarning qatorlari ning ikkilik ko'rinishidagilarga ko'ra taqsimlanadi. Masalan, 21 o'lchamdagi binomial navbatni ko'rib chiqing. Binar 21 ning ifodasi 10101 va binomial navbatda daraxtlar mavjud 0, 2 va 4-darajali (mos ravishda 1, 4 va 16 o'lchamdagi). E'tibor bering, a n o lchamdagi binomial navbat ko pi bilanʻ ʻ log2(n+1) daraxtini o z ichiga oladi. Endi biz binomial navbatlardagi ʻ operatsiyalarni tasvirlashga tayyormiz. Binomial navbatdagi barcha daraxtlar yig'indisi bo'lganligi sababli, biz buni bilamiz binomial navbatdagi minimal element birining ildizi daraxtlardir. Ushbu minimal elementni O(log n) vaqtida skanerlash orqali topishimiz mumkin ildizlar orqali. Navbatga yangi element qo'shish uchun birinchi navbatda yangi singleton daraxtini yarating (ya'ni, 0-darajali binomial daraxt). Biz keyin bizgacha martabani oshirish tartibida mavjud daraxtlar orqali qadam yo'qolgan darajani toping, biz borar ekanmiz, teng darajadagi daraxtlarni bog'laymiz. Kiritish elementni binomial navbatga qo'shish bittani qo'shishga to'g'ri keladi ikkilik raqam, har bir havola tashishga mos keladi. Eng yomon hol bu n = 2k − 1 o lchamdagi navbatga kiritish ʻ bo lib, jami k ni havolalar va O(log n) vaqti talab qiladi. ikkita navbatni ʻ birlashtirish uchun ikkilik qo'shishga o'xshashlik ham amal qiladi. Biz ikkala navbatning daraxtlari orasidan o'tamiz. Bir marta yana, har bir havola bir tashish mos keladi. Buning uchun O (log n) vaqtni ham talab qiladi. 1.1. Eng qiyin operatsiya bu deleteMin . Biz birinchi navbatda daraxtni topamiz minimal ildiz va uni navbatdan olib tashlaymiz. Biz ildizni olib tashlaymiz, lekin keyin o'z farzandlarini navbatga qaytarishi kerak. Biroq, bolalar o'zlari to'g'ri binomial navbatni tashkil qiladi (ya'ni, bir xil darajadagi ikkita daraxt bo'lmagan tepalikli binomial daraxtlar o'rmoni) va shuning uchun navbatning qolgan daraxtlari bilan birlashtirilishi mumkin. Ikkala topilma daraxtni olib 5

O'xshashlar

Brodala-Okasaki uyumi
Qirgʻiz xalqining turmush tarzi va anʼanaviy xoʻjaligi, zamonaviy antropologiyasi
SAMARQAND SUG’DINING ILK O’RTA ASRLAR TARIXI VA MADANIYATIGA DOIR YOZMA MANBALAR
MTTDA BOLALARDA NARSALARNING KATTALIGI VA SHAKLI ORQALI MATEMATIK TASAVVURLARINI SHAKLLANTIRISH
13-14 YOSHLI GANDBOLCHILARNING MASHG’ULOT JARAYONIDA SAKROVCHANLIK JISMONIY QOBILYATINI OSHIRISHDA HARAKATLI O’YINLARDAN FOYDALANISH USULLARI