Min-max үйіндісі - Min-max heap

Min-max үйіндісі
Түрі	екілік ағаш / үйінді
Ойлап тапты	1986
Уақыттың күрделілігі жылы үлкен O белгісі

Жылы Информатика, а минимум үйінді толық болып табылады екілік ағаш мәліметтер құрылымы екеуінің де пайдалылығын біріктіретін а үйінді және а үйінді, яғни ол уақытты үнемі іздеуді және ондағы минималды да, максималды элементтерді де логарифмдік уақытпен жоюды қамтамасыз етеді.^[2] Бұл min-max үйіндісін a-ны жүзеге асыруға арналған өте пайдалы деректер құрылымына айналдырады екі жақты басымдылық кезегі. Екілік мин-үйінділер және максималды-үйінділер сияқты, мин-мак-үймектер де логарифмдік кірістіру мен жоюды қолдайды және оларды сызықтық уақытта құруға болады.^[3] Min-max үйінділері көбінесе an-да жанама түрде ұсынылады массив;^[4] демек, ол деректердің жасырын құрылымы.

The мин-макс үйіндісі меншік: ағаштағы жұп деңгейдегі әрбір түйін оның барлық ұрпақтарынан кем, ал тақтағы тақ деңгейдегі әрбір түйін оның барлық ұрпақтарынан үлкен.^[4]

Сияқты басқа статистикалық операцияларды тиімді қолдау үшін құрылымды жалпылауға болады, мысалы медианалық, жою-медиана,^[2]табу (k) (анықтау kth құрылымдағы ең кіші мән) және операция жою (k) (жою kth құрылымдағы ең кіші мән), кез келген тіркелген мән (немесе мәндер жиыны) үшін к. Бұл соңғы екі операцияны сәйкесінше тұрақты және логарифмдік уақытта жүзеге асыруға болады. Минимумға тапсырыс беру ұғымы максималды немесе минималды тапсырысқа негізделген басқа құрылымдарға таралуы мүмкін, мысалы солшыл ағаштар, деректер құрылымының жаңа (және қуатты) класын құру.^[4] Min-max үйіндісі сыртқы жылдамдықты жүзеге асырған кезде де пайдалы болуы мүмкін.^[5]

Сипаттама

Min-max үйіндісі - a толық екілік ағаш құрамында ауыспалы мин (немесе тіпті) және макс (немесе тақ) деңгейлер. Жұп деңгейлер, мысалы, 0, 2, 4, т.с.с., тақ деңгейлер сәйкесінше 1, 3, 5 және т.с.с. келесі нүктелерде түбір элементі бірінші деңгейде, яғни 0 деп ойлаймыз.

Min-max үйіндісінің мысалы

Min-max үйіндісіндегі әр түйінде мәліметтер мүшесі болады (әдетте осылай аталады) кілт) кімнің мәні мин-макс үйіндісіндегі түйіннің ретін анықтау үшін қолданылады.
The тамыр элемент ең кішкентай/ең үлкен мин-макс үйіндісіндегі элемент.
Екінші деңгейдегі екі элементтің бірі, ол максималды (немесе тақ) деңгей, мин-макс үйіндісіндегі ең үлкен элемент болып табылады
Келіңіздер ${ displaystyle x}$ $х$ мин-макс үйіндісіндегі кез-келген түйін болыңыз.
- Егер ${ displaystyle x}$ минималды деңгейде (немесе тіпті) деңгейде, содан кейін ${ displaystyle x.key}$ түбірі бар ішкі ағаштағы барлық кілттердің арасындағы ең кіші кілт ${ displaystyle x}$ .
- Егер ${ displaystyle x}$ максималды (немесе тақ) деңгейде болса, онда ${ displaystyle x.key}$ түбірі бар субтридадағы барлық кілттердің ішіндегі максималды кілт ${ displaystyle x}$ .
Min (max) деңгейіндегі түйін min (max) түйіні деп аталады.

A max-min үйінді ұқсас түрде анықталады; мұндай үйіндіде максималды мән түбірде, ал ең кіші мән түбір балаларының бірінде сақталады.^[4]

Операциялар

Келесі операцияларда min-max үйіндісі массивте ұсынылған деп есептейміз A [1..N]; The ${ displaystyle ith}$ массивтегі деңгей деңгейде орналасқан түйінге сәйкес келеді ${ displaystyle lfloor log i rfloor}$ үйіндіде.

Құру

Min-max үйіндісін құру Флойдтың үйінді сызықтық уақытты құру алгоритмін бейімдеу арқылы жүзеге асырылады, ол төменнен жоғары қарай жүреді.^[4] Әдеттегі Флойд үйінді алгоритм^[6] келесідей:

FLOYD-BUILD-HEAP функциясы(сағ):    үшін әрбір индекс мен бастап  ${ displaystyle lfloor length (h) / 2 rfloor}$ дейін 1 істеу:        төмен басу(сағ, мен)    қайту сағ

Бұл функцияда, сағ бұл бастапқы массив, оның элементтері min-max үйінді қасиетіне сәйкес реттелмеуі мүмкін. The төмен басу операция (оны кейде деп те атайды) қыру) min-max үйіндісі келесіде түсіндіріледі.

Төмен басу

The төмен басу алгоритм (немесе тамшылау ол қалай аталады ^[4]) келесідей:

PUSH-TOWN функциясы(сағ, мен):    егер мен минималды деңгейде содан кейін:        ТҮСІРУ-МИН(сағ, мен)    басқа:        ТҮСІРУ-МАКС (сағ, мен)    endif

Мин төмен қарай итеріңіз

PUSH-DOWN-MIN функциясы(сағ, мен):    егер мен балалары бар содан кейін:        м : = ең кішкентай баланың немесе немеренің индексі мен        егерм немересі мен содан кейін:            егер сағ [м] < h [i] содан кейін:                айырбастау сағ [м] және h [i]                егер сағ [м] > h [ата-ана (м)] содан кейін:                    айырбастау сағ [м] және h [ата-ана (м)]                endif                ТҮСІРУ-МИН(сағ, м)            endif        басқаша болса сағ [м] < h [i] содан кейін:            айырбастау сағ [м] және h [i]        endif     endif

Максты төмен қарай итеріңіз

Үшін алгоритм басу-төмен-макс push-down-миндікімен бірдей, бірақ барлық салыстыру операторлары керісінше.

PUSH-DOWN-MAX функциясы(сағ, мен):    егер мен балалары бар содан кейін:        м : = ең үлкен баланың немесе немеренің индексі мен        егер м немересі мен содан кейін:            егер сағ [м] > h [i] содан кейін:                айырбастау сағ [м] және h [i]                егер сағ [м] < h [ата-ана (м)] содан кейін:                    айырбастау сағ [м] және h [ата-ана (м)]                endif                ТҮСІРУ-МАКС(сағ, м)            endif        басқаша болса сағ [м] > h [i] содан кейін:            айырбастау сағ [м] және h [i]        endif     endif

Итеративті форма

Рекурсивті шақырулар ретінде басу-мин және басу-төмен-макс құйрық күйінде, бұл функцияларды тұрақты кеңістікте орындалатын тек қайталанатын формаларға түрлендіруге болады:

PUSH-DOWN-MIN-ITER функциясы(сағ, м):    уақыт м балалары бар содан кейін:        i: = m        м : = ең кішкентай баланың немесе немеренің индексі мен        егер м немересі мен содан кейін:            егер сағ [м] < h [i] содан кейін:                айырбастау сағ [м] және h [i]                егер сағ [м] > h [ата-ана (м)] содан кейін:                    айырбастау сағ [м] және h [ата-ана (м)]                endif            endif        басқаша болса сағ [м] < h [i] содан кейін:            айырбастау сағ [м] және h [i]        басқа            үзіліс endif     аяқталды

Кірістіру

Min-max үйіндісіне элемент қосу үшін келесі әрекеттерді орындаңыз:

Қажетті кілтті (соңына) min-max үйіндісін көрсететін массивке қосыңыз. Бұл үйінділердің минимум қасиеттерін бұзуы мүмкін, сондықтан үйінділерді реттеу керек.
Жаңа кілтті ата-анасымен салыстырыңыз:
1. Егер оның ата-анасынан аз (үлкен) екендігі анықталса, онда бұл үйінді тамырына жету жолындағы максималды (мин) деңгейлердегі барлық басқа түйіндерге қарағанда аз (үлкен). Енді мин (макс) деңгейдегі түйіндердің бар-жоғын тексеріңіз.
2. Жаңа түйіннен түбірге дейінгі жол (тек мин (макс) деңгейлерді ескере отырып) кірістіруге дейінгідей кему (өсу) ретімен болуы керек. Сонымен, бізге осы түйінге жаңа түйінді екілік енгізу қажет. Техникалық тұрғыдан жаңа түйінді ата-анасымен ауыстыру оңайырақ, ал ата-анасы үлкен (аз).

Бұл процесс шақыру арқылы жүзеге асырылады итеру төменде сипатталған алгоритм жаңа кілт индексінде.

Жоғары көтеріңіз

The итеру алгоритм (немесе көпіршік ол қалай аталады ^[7]) келесідей:

PUSH-UP функциясы(сағ, мен):    егер мен түбір емес содан кейін:        егер мен мин деңгейінде содан кейін:            егер h [i]> h [ата-ана (i)] содан кейін:                айырбастау h [i] және h [ата-ана (i)]                PUSH-UP-MAX(h, ата-ана (i))            басқа:                ИТУ-ЖАҢА МИН(сағ, мен)            endif        басқа:            егер h [i]  содан кейін:                айырбастау h [i] және h [ата-ана (i)]                ИТУ-ЖАҢА МИН(h, ата-ана (i))            басқа:                PUSH-UP-MAX(сағ, мен)            endif        endif    endif

Минималды түртіңіз

PUSH-UP-MIN функциясы(сағ, мен):    егер мен атасы мен әжесі бар және h [i]  содан кейін:        айырбастау h [i] және h [атасы (и)]        ИТУ-ЖАҢА МИН(с, атасы (і))    endif

Push Up Max

Сияқты төмен басу операциялар, басу-макс ұқсас басу-мин, бірақ салыстыру операторлары ауыстырылды:

PUSH-UP-MAX функциясы(сағ, мен):    егер мен атасы мен әжесі бар және h [i]> h [атасы (i)] содан кейін:        айырбастау h [i] және h [атасы (и)]        PUSH-UP-MAX(с, атасы (і))    endif

Итеративті форма

Рекурсивті шақырулар ретінде басу-мин және басу-макс құйрық күйінде, бұл функцияларды сонымен қатар тұрақты кеңістікте орындалатын тек қайталанатын формаларға түрлендіруге болады:

PUSH-UP-MIN-ITER функциясы(сағ, мен):    уақыт мен атасы мен әжесі бар және h [i]  содан кейін:        айырбастау h [i] және h [атасы (и)]        мен := ата (ә)    аяқталды

Мысал

Мұнда элементті Min-Max үйіндісіне енгізудің бір мысалы келтірілген.

Бізде келесі мин-макс үйіндісі бар және 6 мәні бар жаңа түйін енгізгіміз келеді деп айтыңыз.

Бастапқыда 6-түйін 11-ші түйіннің оң жақ перзенті ретінде енгізіледі. 6-дан 11-ден кіші, сондықтан ол максималды деңгейлердегі барлық түйіндерден аз (41), және біз тек мин деңгейлерді (8 және 11) тексеруіміз керек ). Біз 6 және 11 түйіндерін ауыстырып, содан кейін 6 және 8-ді ауыстыруымыз керек. Осылайша, 6 үйінділердің түбірлік орнына ауысады, бұрынғы 8 түбірлер 11-дің орнына төмен түсіп, 11-ден 8-ге дұрыс бала шығады.

6-ның орнына 81 жаңа түйінін қосуды қарастырайық. Бастапқыда түйін 11-түйіннің оң жақ перзенті ретінде енгізіледі. 81 11-ден үлкен, сондықтан кез-келген мин деңгейлерінің кез-келген түйінінен үлкен (8 және 11). Енді бізге тек максималды деңгейлердегі түйіндерді тексеру керек (41) және бір своп жасау керек.

Минимумды табыңыз

Min-Max үймесінің минималды түйіні (немесе кнопкалар қайталанған жағдайда минималды түйін) әрқашан түбірде орналасады. Минимумды табу - бұл түбірлерді қайтаратын уақытша тривиальды операция.

Максимумды табыңыз

Min-Max үймесінің максималды түйіні (немесе қайталанатын кілттер жағдайындағы максималды түйін) әрдайым бірінші максималды деңгейде орналасады - яғни, тамырдың жақын балаларының бірі ретінде. Максимумды табыңыз, осылайша түбірдің екі баласының қайсысы үлкен екенін анықтау үшін ең көп дегенде бір салыстыру қажет, сонымен қатар бұл уақытша жұмыс.

Минималды алып тастаңыз

Минималды алып тастау - бұл массивтегі индексі белгілі ерікті түйінді жоюдың ерекше жағдайы. Бұл жағдайда массивтің соңғы элементі алынып тасталады (массивтің ұзындығын азайтады) және массивтің басында тамырды ауыстыру үшін қолданылады. төмен басу содан кейін үйінді сипатын қалпына келтіру үшін root индексіне шақырылады ${ displaystyle O ( log _ {2} (n))}$ уақыт.

Максимумды алып тастаңыз

Максимумды алып тастау - белгілі индексі бар ерікті түйінді жоюдың ерекше жағдайы. Find Maximum операциясындағыдай, түбірдің максималды баласын анықтау үшін жалғыз салыстыру қажет, содан кейін ол массивтің соңғы элементімен ауыстырылады және төмен басу содан кейін үйінді сипатын қалпына келтіру үшін ауыстырылған максимум индексі бойынша шақырылады.

Кеңейтімдер

Min-max-median heap - бұл құрылымға алғашқы жарияланымда ұсынылған, min-max үймесінің нұсқасы, ол әрекеттерді қолдайды статистикалық ағашқа тапсырыс беру.
Әдебиеттер тізімі

^ Мишель. «Джим». Stack overflow. Алынған 8 қыркүйек 2016.
^ ^а ^б АТКИНСОН, М.Д; SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыланған басымдық кезектері» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.
^ АТКИНСОН, М.Д; SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыланған басымдық кезектері» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.
^ ^а ^б ^c ^г. ^e ^f АТКИНСОН, М. SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыға бірдей кезек» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.
^ Гоннет, Гастон Х .; Баеза-Йейтс, Рикардо (1991). Алгоритмдер мен мәліметтер құрылымы туралы анықтама: Паскальда және С. ISBN 0201416077.
^ K. Paparrizos, Ioannis (2011). «Флойдтың үйінді салу алгоритмін салыстырудың ең нашар жағдайына қатаң шектеу». arXiv:1012.0956. Бибкод:2010arXiv1012.0956P. Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
^ АТКИНСОН, М.Д; SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыға бірдей кезек» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.

[How_to_perform_a_general_deletion_operation_on_a_min-max_heap?-1] Мишель. «Джим». Stack overflow. Алынған 8 қыркүйек 2016.

[:0-2] а ^б АТКИНСОН, М.Д; SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыланған басымдық кезектері» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.

[3] АТКИНСОН, М.Д; SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыланған басымдық кезектері» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.

[:1-4] а ^б ^c ^г. ^e ^f АТКИНСОН, М. SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыға бірдей кезек» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.

[5] Гоннет, Гастон Х .; Баеза-Йейтс, Рикардо (1991). Алгоритмдер мен мәліметтер құрылымы туралы анықтама: Паскальда және С. ISBN 0201416077.

[6] K. Paparrizos, Ioannis (2011). «Флойдтың үйінді салу алгоритмін салыстырудың ең нашар жағдайына қатаң шектеу». arXiv:1012.0956. Бибкод:2010arXiv1012.0956P. Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)

[7] АТКИНСОН, М.Д; SACK, J.-R; САНТОРО, Н .; STROTHOTTE, T. (1986). Мунро, Ян (ред.) «Мин-Макс үйінділері және жалпыға бірдей кезек» (PDF). ACM байланысы. 29 (10): 996–1000. дои:10.1145/6617.6621.

[1]

[2]

[3]

[4]

[5]

[6]

[7]