Min-max uyum - Min-max heap

Min-max uyum
Turi	ikkilik daraxt / uyum
Ixtiro qilingan	1986
Vaqtning murakkabligi yilda katta O yozuvlari

Yilda Kompyuter fanlari, a min-max uyum to'liq ikkilik daraxt ma'lumotlar tuzilishi ikkalasining ham foydaliligini birlashtirgan a uyum va a maksimal uyum, ya'ni undagi minimal va maksimal elementlarning doimiy vaqtini olish va logaritmik vaqtni olib tashlashni ta'minlaydi.^[2] Bu min-max yig'indisini a-ni amalga oshirish uchun juda foydali ma'lumotlar tuzilishiga aylantiradi ikki tomonlama ustuvor navbat. Ikkilik min-heaps va max-heaps singari, min-max heaps ham logaritmik kiritishni va o'chirishni qo'llab-quvvatlaydi va ularni chiziqli vaqt ichida qurish mumkin.^[3] Min-max uyumlari ko'pincha to'g'ridan-to'g'ri an shaklida ifodalanadi qator;^[4] shuning uchun u an deb nomlanadi yashirin ma'lumotlar tuzilishi.

The min-max uyum mulk: daraxtdagi juft darajadagi har bir tugun barcha avlodlaridan kam, daraxtdagi toq darajadagi har bir tugun barcha avlodlaridan kattaroq.^[4]

Kabi boshqa buyurtma-statistik operatsiyalarni samarali qo'llab-quvvatlash uchun tuzilmani umumlashtirish mumkin median, O'chirish-mediani,^[2]topish (k) (ni aniqlang kth tuzilishdagi eng kichik qiymat) va operatsiya o'chirish (k) (o'chirish kth har qanday sobit qiymati (yoki qiymatlar to'plami) uchun tuzilishdagi eng kichik qiymat) k. Ushbu so'nggi ikkita operatsiyani mos ravishda doimiy va logaritmik vaqt ichida amalga oshirish mumkin. Min-max buyurtma tushunchasi, masalan, maksimal yoki min buyurtma asosida boshqa tuzilmalarga ham tarqalishi mumkin chap daraxtlar, ma'lumotlar tuzilmalarining yangi (va kuchliroq) sinfini yaratish.^[4] Min-max uyum tashqi tezkor kortni amalga oshirishda ham foydali bo'lishi mumkin.^[5]

Tavsif

Min-max uyum a to'liq ikkilik daraxt o'zgaruvchan o'z ichiga oladi min (yoki hatto) va maksimal (yoki g'alati) darajalar. Hatto darajalar, masalan, 0, 2, 4 va boshqalar, va g'alati darajalar mos ravishda 1, 3, 5 va boshqalar. Keyingi nuqtalarda ildiz elementi birinchi darajadagi, ya'ni 0 bo'lgan deb taxmin qilamiz.

Min-max uyumining misoli

Min-max uyumidagi har bir tugunda ma'lumotlar a'zosi mavjud (odatda shunday nomlanadi) kalit) kimning qiymati min-max uyumidagi tugun tartibini aniqlash uchun ishlatiladi.
The ildiz element eng kichik/eng buyuk min-max uyumidagi element.
Maks (yoki g'alati) daraja bo'lgan ikkinchi darajadagi ikkita elementning biri min-max uyumidagi eng katta element
Ruxsat bering ${ displaystyle x}$ $x$ min-max uyumidagi har qanday tugun bo'ling.
- Agar ${ displaystyle x}$ keyin min (yoki hatto) darajada bo'ladi ${ displaystyle x.key}$ root bilan subtree tarkibidagi barcha tugmachalar orasida minimal kalit ${ displaystyle x}$ .
- Agar ${ displaystyle x}$ keyin maksimal (yoki g'alati) darajada bo'ladi ${ displaystyle x.key}$ root bilan subtree tarkibidagi barcha tugmachalar orasidagi maksimal kalit ${ displaystyle x}$ .
Min (max) darajadagi tugun min (max) tugun deb ataladi.

A max-min uyum o'xshash tarzda belgilanadi; bunday uyumda maksimal qiymat ildizda, eng kichik qiymat esa ildiz farzandlaridan birida saqlanadi.^[4]

Amaliyotlar

Quyidagi operatsiyalarda min-max uyum massivda ifodalangan deb taxmin qilamiz A [1..N]; The ${ displaystyle ith}$ massivdagi joylashuv darajadagi tugunga to'g'ri keladi ${ displaystyle lfloor log i rfloor}$ uyumda

Qurmoq

Min-max uyumini yaratish Floydning chiziqli vaqtli yig'ish algoritmini moslashtirish orqali amalga oshiriladi, u pastdan yuqoriga qarab davom etadi.^[4] Oddiy Floyd yig'ish algoritm^[6] quyidagicha ketadi:

FLOYD-BUILD-HEAP funktsiyasi(h):    uchun har bir indeks men dan  ${ displaystyle lfloor length (h) / 2 rfloor}$ pastga 1 bajaring:        pastga tushirish(h, men)    qaytish h

Ushbu funktsiyada, h boshlang'ich massiv bo'lib, uning elementlari min-max heap xususiyatiga ko'ra buyurtma berilishi mumkin emas. The pastga tushirish operatsiya (ba'zida u ham deyiladi qirib tashlamoq) min-max uyumining keyingi qismi tushuntiriladi.

Pastga suring

The pastga tushirish algoritm (yoki pastga tushirish deb nomlangan ^[4]) quyidagicha:

PUSH-DOWN funktsiyasi(h, men):    agar men min darajasida keyin:        PUSH-DOWN-MIN(h, men)    boshqa:        PUSH-DOWN-MAX (h, men)    endif

Minni pastga suring

PUSH-DOWN-MIN funktsiyasi(h, men):    agar men bolalari bor keyin:        m : = eng kichik bola yoki nabiraning ko'rsatkichi men        agarm ning nabirasi men keyin:            agar h [m] < h [i] keyin:                almashtirish h [m] va h [i]                agar h [m] > h [ota-ona (m)] keyin:                    almashtirish h [m] va h [ota-ona (m)]                endif                PUSH-DOWN-MIN(h, m)            endif        boshqa bo'lsa h [m] < h [i] keyin:            almashtirish h [m] va h [i]        endif     endif

Maksni pastga suring

Uchun algoritm pastga tushirish-max push-down-min bilan bir xil, ammo barcha taqqoslash operatorlari teskari.

PUSH-DOWN-MAX funktsiyasi(h, men):    agar men bolalari bor keyin:        m : = eng katta bola yoki nabiraning ko'rsatkichi men        agar m ning nabirasi men keyin:            agar h [m] > h [i] keyin:                almashtirish h [m] va h [i]                agar h [m] < h [ota-ona (m)] keyin:                    almashtirish h [m] va h [ota-ona (m)]                endif                PUSH-DOWN-MAX(h, m)            endif        boshqa bo'lsa h [m] > h [i] keyin:            almashtirish h [m] va h [i]        endif     endif

Takroriy shakl

Rekursiv qo'ng'iroqlar kabi pastga tushirish-min va pastga tushirish-max quyruq holatidadir, bu funktsiyalar ahamiyatsiz doimiy kosmosda bajariladigan takrorlanadigan shakllarga aylantirilishi mumkin:

PUSH-DOWN-MIN-ITER funktsiyasi(h, m):    esa m bolalari bor keyin:        i: = m        m : = eng kichik bola yoki nabiraning ko'rsatkichi men        agar m ning nabirasi men keyin:            agar h [m] < h [i] keyin:                almashtirish h [m] va h [i]                agar h [m] > h [ota-ona (m)] keyin:                    almashtirish h [m] va h [ota-ona (m)]                endif            endif        boshqa bo'lsa h [m] < h [i] keyin:            almashtirish h [m] va h [i]        boshqa            tanaffus endif     tugadi

Kiritish

Min-max uyumiga element qo'shish uchun quyidagi amallarni bajaring:

Min-max uyumini ifodalovchi massivga kerakli tugmachani (oxiriga) ilova qiling. Bu, ehtimol, min-max yig'ish xususiyatlarini buzadi, shuning uchun biz uyumni sozlashimiz kerak.
Yangi kalitni ota-onasi bilan taqqoslang:
1. Agar u ota-onadan kam (kattaroq) deb topilsa, unda u uyum ildiziga boradigan maksimal (min) darajadagi barcha boshqa tugunlardan kamroq (katta) bo'ladi. Endi min (max) darajadagi tugunlarni tekshiring.
2. Yangi tugundan ildizga yo'l (faqat min (max) darajalarni hisobga olgan holda) qo'shilishdan oldin bo'lgani kabi kamayib (ko'tarilgan) tartibda bo'lishi kerak. Shunday qilib, biz ushbu tugunga yangi tugunning ikkilik qo'shilishini amalga oshirishimiz kerak. Texnik jihatdan yangi tugunni ota-onasi bilan almashtirish osonroq, ota-onasi kattaroq (kamroq).

Ushbu jarayonni chaqirish orqali amalga oshiriladi tepaga itarish quyida keltirilgan algoritm yangi qo'shilgan kalit indeksida.

Tepaga itarish

The tepaga itarish algoritm (yoki qabariq deb nomlangan ^[7]) quyidagicha:

PUSH-UP funktsiyasi(h, men):    agar men ildiz emas keyin:        agar men min darajasida keyin:            agar h [i]> h [ota-ona (i)] keyin:                almashtirish h [i] va h [ota-ona (i)]                PUSH-UP-MAX(h, ota-ona (i))            boshqa:                PUSH-UP-MIN(h, men)            endif        boshqa:            agar h [i]  keyin:                almashtirish h [i] va h [ota-ona (i)]                PUSH-UP-MIN(h, ota-ona (i))            boshqa:                PUSH-UP-MAX(h, men)            endif        endif    endif

Push Up Min

PUSH-UP-MIN funktsiyasi(h, men):    agar men bobosi va buvisi bor va h [i]  keyin:        almashtirish h [i] va h [bobosi (i)]        PUSH-UP-MIN(h, bobosi (i))    endif

Maksimal surish

Bilan bo'lgani kabi pastga tushirish operatsiyalar, push-up-max bilan bir xil surish-min, lekin taqqoslash operatorlari bilan teskari:

PUSH-UP-MAX funktsiyasi(h, men):    agar men bobosi va buvisi bor va h [i]> h [bobosi (i)] keyin:        almashtirish h [i] va h [bobosi (i)]        PUSH-UP-MAX(h, bobosi (i))    endif

Takroriy shakl

Rekursiv qo'ng'iroqlar kabi surish-min va push-up-max quyruq holatidadir, bu funktsiyalar, shuningdek, doimiy ravishda bajariladigan sof iterativ shakllarga aylantirilishi mumkin:

PUSH-UP-MIN-ITER funktsiyasi(h, men):    esa men bobosi va buvisi bor va h [i]  keyin:        almashtirish h [i] va h [bobosi (i)]        men := bobosi (i)    tugadi

Misol

Min-Max Heap-ga element qo'shish uchun bitta misol.

Bizda quyidagi min-max yig'indisi bor va 6-qiymatga ega yangi tugunni kiritishni xohlaymiz.

Dastlab, 6-tugun 11-tugunning o'ng farzandi sifatida kiritiladi. 6-dan 11 gacha, shuning uchun u maksimal darajadagi barcha tugunlardan kamroq (41) va biz faqat minimal darajalarni (8 va 11) tekshirishimiz kerak ). Biz 6 va 11 tugunlarni almashtirishimiz kerak, so'ngra 6 va 8 ni almashtirishimiz kerak. Shunday qilib, 6 uyumning ildiz holatiga ko'chiriladi, avvalgi ildiz 8, 11 o'rnini bosish uchun pastga siljiydi va 11 yosh 8 ga to'g'ri keladi.

6 tugmachasi o'rniga 81 yangi tugunni qo'shishni o'ylab ko'ring. Dastlab, tugun 11 tugunning o'ng farzandi sifatida kiritildi. 81 11 dan katta, shuning uchun u har qanday min darajadagi har qanday tugundan kattaroq (8 va 11). Endi biz faqat maksimal darajadagi tugunlarni tekshirishimiz kerak (41) va bitta almashtirishni amalga oshirishimiz kerak.

Minimalni toping

Min-Max Heap-ning minimal tuguni (yoki kalitlarning nusxasi takrorlanadigan bo'lsa, minimal tugun) har doim ildizda joylashgan. Shunday qilib, Minimumni toping, shunchaki ildizlarni qaytaradigan ahamiyatsiz doimiy vaqt operatsiyasi.

Maksimalni toping

Min-Max Heap-ning maksimal tuguni (yoki takrorlanadigan tugmachalarda maksimal tugun) har doim birinchi max darajasida - ya'ni ildizning bevosita farzandlaridan biri sifatida joylashgan. Maksimalni toping, shuning uchun ildizning ikkita farzandidan qaysi biri kattaroqligini va shu bilan birga doimiy vaqt operatsiyasini aniqlash uchun eng ko'p taqqoslash kerak.

Minimalni olib tashlang

Minimalni olib tashlash - bu faqat massivdagi indekslari ma'lum bo'lgan o'zboshimchalik bilan tugunni olib tashlashning maxsus holati. Bunday holda, massivning oxirgi elementi olib tashlanadi (massiv uzunligini qisqartiradi) va massivning boshida, ildizni almashtirish uchun ishlatiladi. pastga tushirish keyin heap xususiyatini tiklash uchun root indeksiga chaqiriladi ${ displaystyle O ( log _ {2} (n))}$ vaqt.

Maksimalni olib tashlang

Maksimalni olib tashlash yana bir bor ma'lum indeks bilan o'zboshimchalik bilan tugunni olib tashlashning alohida holatidir. Find Maximum operatsiyasida bo'lgani kabi, ildizning maksimal bolasini aniqlash uchun bitta taqqoslash talab qilinadi, shundan so'ng u massivning oxirgi elementi bilan almashtiriladi va pastga tushirish keyin to'plangan xususiyatni tiklash uchun almashtirilgan maksimal indeksiga chaqiriladi.

Kengaytmalar

Min-max-median heap - bu strukturaning dastlabki nashrida taklif qilingan min-max uyumining bir variantidir, bu operatsiyalarni qo'llab-quvvatlaydi. buyurtma statistik daraxt.
Adabiyotlar

^ Mischel. "Jim". Stack overflow. Olingan 8 sentyabr 2016.
^ ^a ^b ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.
^ ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.
^ ^a ^b ^v ^d ^e ^f ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.
^ Gonnet, Gaston X.; Baeza-Yeyts, Rikardo (1991). Algoritmlar va ma'lumotlar tuzilmalari bo'yicha qo'llanma: Paskal va C tillarida. ISBN 0201416077.
^ K. Paparrizos, Ioannis (2011). "Floydning uyma-uy qurish algoritmini taqqoslashning eng yomon holatlari soniga qat'iy bog'liqlik". arXiv:1012.0956. Bibcode:2010arXiv1012.0956P. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
^ ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.

[How_to_perform_a_general_deletion_operation_on_a_min-max_heap?-1] Mischel. "Jim". Stack overflow. Olingan 8 sentyabr 2016.

[:0-2] ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.

[3] ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.

[:1-4] v ^d ^e ^f ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.

[5] Gonnet, Gaston X.; Baeza-Yeyts, Rikardo (1991). Algoritmlar va ma'lumotlar tuzilmalari bo'yicha qo'llanma: Paskal va C tillarida. ISBN 0201416077.

[6] K. Paparrizos, Ioannis (2011). "Floydning uyma-uy qurish algoritmini taqqoslashning eng yomon holatlari soniga qat'iy bog'liqlik". arXiv:1012.0956. Bibcode:2010arXiv1012.0956P. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)

[7] ATKINSON, M. D; SACK, J.-R; SANTORO, N .; STROTOTTE, T. (1986). Munro, Yan (tahrir). "Min-Maks uyumlari va umumiy ustuvor navbat" (PDF). ACM aloqalari. 29 (10): 996–1000. doi:10.1145/6617.6621.

[1]

[2]

[3]

[4]

[5]

[6]

[7]