Кеп - Queap

K = 6 және n = 9 мәндері бар Que Q

Жылы Информатика, а кезек Бұл кезек кезегі мәліметтер құрылымы. Мәліметтер құрылымы ерікті элементтерді кірістіруге және жоюға, сондай-ақ ең маңызды элементті алуға мүмкіндік береді. Әрбір жою қажет амортизацияланған уақыт жойылған элементтен гөрі құрылымда ұзақ уақыт болған заттар санындағы логарифмдік. Енгізулер тұрақты амортизацияланған уақытты алады.

Мәліметтер құрылымы а қосарланған тізбе және а 2-4 ағаш мәліметтер құрылымы, әрқайсысы өзінің минималды басымдылық элементін қадағалау үшін өзгертілген. Құрылымның негізгі әрекеті - жаңадан енгізілген элементтерді қосарланған тізімде сақтау, бұл жойылған кезде тізім элементтерінің бірін алып тастағанша, сол кезде олардың барлығы 2-4 ағашқа көшіріледі. 2-4 ағаш өз элементтерін әдеттегідей басымдықпен сұрыпталған ретпен емес, енгізу ретімен сақтайды.

Деректер құрылымын да, оның атын да ойлап тапты Джон Яконо және Стефан Лангерман.[1]

Сипаттама

Кезек дегеніміз - бұл элементтерді амортизацияланған уақытқа O (1) енгізетін және O ішіндегі минималды элементті алып тастайтын басымды кезек (log (к + 2)) егер бар болса к шығарылатын элементтен гөрі ұзақ уақыт үйіндіде болған заттар. Кезек кезегінде тұрған қасиет бар: элементті іздеу уақыты х O (lg.) q(х)) қайда q(х) тең n − 1 − w(х) және w(х) - іздеу, кірістіру немесе жою сияқты операциялар арқылы қол жеткізілген нақты элементтердің саны. q(х) содан бері қанша элементтерге қол жеткізілмегені ретінде анықталады хсоңғы кіру. Шынында да, кезек сипаты - бұл splay tree жұмысының жиынтық қасиетінің толықтырушысы: элементті іздеуге арналған уақыт х O (lg.) w(х)).

Кестені екі мәліметтер құрылымымен ұсынуға болады: екі еселенген тізбемен және 2-4 ағаштың өзгертілген нұсқасымен. Екі еселенген тізім, L, кірістіру және орналастыру-мин операциялары сериясы үшін қолданылады. Кесте көрсеткішті тізімде сақталған минималды элементке сақтайды. Элемент қосу үшін х тізімге қосу л, элемент х тізімнің соңына және элементте бит айнымалысына қосылады х біреуіне орнатылған. Бұл әрекет элементтің не тізімде, не 2-4 ағашта екенін анықтау үшін жасалады.

2-4 ағаш жою операциясы орын алғанда қолданылады. Егер элемент болса х қазірдің өзінде ағашта Т, тармақ 2-4 ағашты жою операциясының көмегімен жойылады. Әйтпесе, элемент х тізімде L (бит айнымалысының орнатылғандығын тексеру арқылы жасалады). Тізімде сақталған барлық элементтер L әр элементтің биттік айнымалысын нөлге теңестіріп, 2-4 ағашқа қосылады. х содан кейін жойылады Т.

Квап іздеу ағашын емес, тек 2-4 ағаш құрылымының қасиеттерін пайдаланады. Өзгертілген 2-4 ағаш құрылымы келесідей. Тізім делік L келесі элементтер жиынтығына ие: . Жою әрекеті шақырылған кезде, элементтер жиынтығы L содан кейін 2-4 ағаштың жапырақтарына ретімен қосылады, шексіз кілті бар жалған жапырақ жалғасады. Әрбір ішкі түйін Т көрсеткіші бар , бұл кіші тармақтағы кіші тармақты көрсетеді v. Жолдағы әрбір ішкі түйін P тамырдан көрсеткіші бар , ол ең кіші кілтке нұсқайды . The жолдағы әрбір ішкі түйіннің көрсеткіштері P еленбейді. Кесектің көрсеткіші бар , бұл ең кіші элементті көрсетеді Т.

Кваптарды қолдану ерекше маңызды оқиғалардың бірегей жиынтығын және өңдеу үшін ең жоғары басымдылықты алуды қамтиды.

Операциялар

Келіңіздер мин қосарланған тізімдегі минималды элементті көрсететін көрсеткіш бол L, 2-4 ағашта сақталатын минималды элемент болуы керек, Т, к ішінде сақталған элементтер саны болуы керек Т, және n кезекте сақталған элементтердің жалпы саны болуы керек Q. Операциялар келесідей:

Жаңа (Q): Жаңа бос кезекті бастайды.

Бос қос тізімді бастаңыз L және 2-4 ағаш Т. Орнатыңыз к және n нөлге дейін.

Кірістіру (Q, x): Элементті қосыңыз х секіру Q.

Элементті салыңыз х тізімде L. Битті элементке қойыңыз х элементтің тізімде екенін көрсету үшін біреуіне L. Жаңартыңыз мин көрсеткіш, егер х тізімдегі ең кішкентай элемент. Өсу n 1-ге

Минимум (Q): Сілтегішті ең кіші элементке шығарып алыңыз Q.

Егер кілт (минЛ) < кілт(), қайтару мин. Әйтпесе қайтыңыз .

Жою (Q, x): Х элементін кезектен тыс алып тастаңыз Q.

Егер элементтің биті болса х біреуіне қойылады, элемент тізімде сақталады L. Барлық элементтерді қосыңыз L дейін Т, әрбір элементтің битін нөлге теңестіру. Әрбір элемент ең дұрыс баланың ата-анасына қосылады Т 2-4 ағаштың кірістіру әрекетін қолдана отырып. L бос болады. Жаңарту барлық түйіндерге арналған көрсеткіштер v оның балалары жаңа / өзгертілген және ата-ана түбірге тең болғанша келесі ата-анамен бірге процесті қайталаңыз. Түбірден түйінге дейін жүріңіз және жаңартыңыз құндылықтар. Орнатыңыз к тең n.
Егер элементтің биті болса х нөлге орнатылған, х жапырағы Т. 2-4 ағашты жою әрекетін пайдаланып x-ті жойыңыз. Түйіннен басталады х, жүріңіз Т түйінге , жаңарту және көрсеткіштер. N және k-ді 1-ге азайту.

DeleteMin (Q): Кітаптан ең кіші элементті жойыңыз және қайтарыңыз Q.

Шақыру Минимум (Q) жұмыс. Операция қайтарылады мин. Шақыру Жою (Q, мин) жұмыс. Қайту мин.

CleanUp (Q): Тізімдегі барлық элементтерді жойыңыз L және ағаш Т.

Тізімдегі бірінші элементтен бастап L, әр түйінді жойып, тізімді өтіңіз.
Ағаштың тамырынан бастап Т, көмегімен ағашты айналып өтіңіз тапсырыстан кейінгі жүру алгоритм, ағаштағы әрбір түйінді жою.

Талдау

Жұмыс уақыты талданылады амортизациялық талдау. Кезектілік Q үшін әлеуетті функция болады қайда .

Кірістіру (Q, x): Операция құны O (1). Тізімнің мөлшері L өседі, потенциал біршама тұрақтыға артады c.

Минимум (Q): Операция деректер құрылымын өзгертпейді, сондықтан амортизацияланған шығын оның нақты құнына тең, O (1).

Жою (Q, x): Екі жағдай бар.

1-жағдай

Егер х ағашта Т, онда амортизацияланған құн өзгертілмейді. Жою әрекеті O (1) амортизацияланған 2-4 ағаш. Бастап х ағаштан шығарылды, және көрсеткіштер жаңартуды қажет етуі мүмкін. Ең көп болады жаңартулар.

2-жағдай

Егер х тізімде L, содан кейін барлық элементтер L енгізілген Т. Бұл өзіндік құны бар тұрақты а, 2-4 ағаштың үстінен амортизацияланған. Енгізіп, жаңартқаннан кейін және көрсеткіштер, өткізілген жалпы уақыт шектеледі . Екінші амал - жою х бастап Т, және х-ден жолға өту , түзету және құндылықтар. Уақыт көп дегенде өткізіледі . Егер , онда амортизацияланған шығын болады .Жою (Q, x): амортизацияланған құнын қосу болып табылады Минимум (Q) және Жою (Q, x), қайсысы .

Код мысалы

Кішкентай Java кезекті жүзеге асыру:

қоғамдық сынып Кеп{    қоғамдық int n, к;    қоғамдық Тізім<Элемент> л; // Элемент - бұл жалпы мәліметтер типі.    қоғамдық QueapTree т;     // Queap мақсатында өзгертілген 2-4 ағаш    қоғамдық Элемент мин;    жеке Кеп() {        n = 0;        к = 0;        л = жаңа Байланысты тізім<Элемент>();        т = жаңа QueapTree();    }    қоғамдық статикалық Кеп Жаңа() {        қайту жаңа Кеп();    }    қоғамдық статикалық жарамсыз Кірістіру(Кеп Q, Элемент х) {        егер (Q.n == 0)            Q.мин = х;        Q.л.қосу(х);        х.inList = шын;        егер (х.салыстыру(Q.мин) < 0)            Q.мин = х;    }    қоғамдық статикалық Элемент Минималды(Кеп Q) {        // t - 2-4 ағаш, ал x0 - ағаш түйіндері.        егер (Q.мин.салыстыру(Q.т.x0.резюме.кілт) < 0)            қайту Q.мин;        қайту Q.т.x0.резюме.кілт;    }    қоғамдық статикалық жарамсыз Жою(Кеп Q, QueapNode х) {        Q.т.deleteLeaf(х);        --Q.n;        --Q.к;    }    қоғамдық статикалық жарамсыз Жою(Кеп Q, Элемент х) {        QueapNode n;        егер (х.inList) {            // тізімдегі барлық элементтердің inList параметрін жалғанға орнатыңыз            n = Q.т.insertList(Q.л, х);            Q.к = Q.n;            Жою(Q, n);        }        басқа егер ((n = Q.т.x0.резюме).кілт == х)            Жою(Q, n);    }    қоғамдық статикалық Элемент DeleteMin(Кеп Q) {        Элемент мин = Минималды(Q);        Жою(Q, мин);        қайту мин;    }}

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Яконо, Джон; Лангерман, Стефан (2005). «Кептер». Алгоритмика. Спрингер. 42 (1): 49–56. дои:10.1007 / s00453-004-1139-5.