Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
В комп'ютерних науках, двостороння черга з пріоритетом (ДЧП) або ж двостороння купа це структура даних подібна до черги з пріорітетом чи купи, яка дозволяє ефективно вилучати з неї максимальний та мінімальний елемент відносно пріорітету об'єктів, які знаходяться у цій структурі. Кожен елемент у ДЧП має свій пріорітет і значення. У ДЧП можливо вилучати елементи як у порядку зростання, так і в порядку спадання.
Функції
Двостороння черга з пріоритетом дозволяє такі операції:
- isEmpty()
- Перевіряє, чи ДЧП пуста і, якщо так, то повертає значення True.
- size()
- Повертає кількість елементів у даній ДЧП.
- getMin()
- Повертає елемент з найнижчим пріорітетом.
- getMax()
- Повертає елемент з найвищим пріорітетом.
- put(x)
- Додає елемент x до ДЧП.
- removeMin()
- Вилучає елемент з найнижчим пріорітетом і повертає його.
- removeMax()
- Вилучає елемент з найвищим пріорітетом і повертає його.
Якщо операція проводиться над двома елементами з однаковою пріорітетністю, то буде вибрано той, який було додано раніше. Також, пріоритет будь-якого елементу може бути змінено після додавання його у ДЧП.
Реалізація
Двостороння черга з пріоритетом може бути створеною зі збалансованого двійкового дерева пошуку (де елементи з найнижчим і найвищим пріорітетом це крайній лівий і правий листки відповідно), або використовуючи такі спеціалізовані структури даних, як [en] чи [en].
Загальними методами отримання черг із двостороннім пріоритетом із звичайних пріоритетних черг є:
Метод подвійної структури
У цьому методі підтримуються дві черги з різними пріоритетами для min та max. Ті самі елементи в обох пріорітетних чергах відображаються за допомогою покажчиків відповідності. Тут мінімальний і максимальний елементи є значеннями, що містяться в кореневих вузлах мінімальної та максимальної купи відповідно.
- Видалення елемента min: Виконайте removemin() у мінімальній купі та remove(значення вузла) у максимальній купі, де значення вузла – це значення у відповідному вузлі в максимальній купі.
- Видалення елемента max: Виконайте removemax() у максимальній купі та remove(значення вузла) у мінімальній купі, де значення вузла – це значення у відповідному вузлі мінімальної купі.
Повна відповідність
Половина елементів знаходиться в мінімальній пріоритетній черці, а інша половина в максимальній пріорітетній черзі. Кожен елемент у min ПЧ має відповідність один до одного з елементом у max ПЧ. Якщо кількість елементів у ДЧП непарна, один із елементів зберігається в буфері. Пріоритет кожного елемента в мінімальній ПЧ буде меншим або дорівнюватиме відповідному елементу в максимальній ПЧ.
Листкова відповідність
У цьому методі лише листові елементи min і max ПЧ утворюють відповідні пари один до одного. Необов’язково, щоб нелисткові елементи були в парі відповідності один до одного.
Інтервальні купи
Окрім вищезгаданих методів відповідності, ДЧП можна ефективно отримати за допомогою інтервальних куп. Інтервальна купа схожа на вбудовану [en], в якій кожен вузол містить два елементи. Це повне двійкове дерево, у якому:
- Лівий елемент менше або дорівнює правому елементу.
- Обидва елементи визначають замкнутий інтервал.
- Інтервал, представлений будь-яким вузлом, крім кореневого, є підінтервалом батьківського вузла.
- Елементи з лівого боку визначають min купу.
- Елементи з правого боку визначають max купу.
Залежно від кількості елементів можливі два випадки -
- Парна кількість елементів: У цьому випадку кожен вузол містить два елементи, наприклад, p та q, з p ≤ q. Потім кожен вузол представляється інтервалом [p, q].
- Непарна кількість елементів: У цьому випадку кожен вузол, крім останнього, містить два елементи, представлені інтервалом [p, q], тоді як останній вузол міститиме один елемент і представлений інтервалом [p, p].
Вкладання елемента
Залежно від кількості елементів, які вже присутні в інтервальній купі, можливі наступні випадки:
- Непарна кількість елементів: Якщо кількість елементів у купі інтервалів непарна, новий елемент спочатку вставляється в останній вузол. Потім він послідовно порівнюється з попередніми елементами вузла та перевіряється на відповідність критеріям, суттєвим для інтервальної купи, як зазначено вище. У випадку, якщо елемент не задовольняє жоден з критеріїв, його переміщують з останнього вузла до кореня, поки не будуть виконані всі умови.
- Парна кількість елементів: Якщо кількість елементів парна, то для вставки нового елемента створюється додатковий вузол. Якщо елемент потрапляє ліворуч від батьківського інтервалу, він вважається в min купі, а якщо елемент потрапляє праворуч від батьківського інтервалу, він розглядається в max купі. Далі він послідовно порівнюється і переміщується від останнього вузла до кореня, поки не будуть задоволені всі умови для інтервальної купи. Якщо елемент знаходиться в інтервалі самого батьківського вузла, процес тоді зупиняється і переміщення елементів не відбувається.
Час, необхідний для вставки елемента, залежить від кількості рухів, необхідних для виконання всіх умов і є O(log n).
Вилучення елемента
- Min елемент: В інтервальної купі мінімальним елементом є елемент з лівого боку від кореневого вузла. Цей елемент видаляється та повертається. Щоб заповнити вакансію, створену зліва від кореневого вузла, елемент з останнього вузла видаляється і знову вставляється в кореневий вузол. Потім цей елемент послідовно порівнюється з усіма лівими елементами низхідних вузлів, і процес зупиняється, коли задовольняються всі умови для інтервальної купи. У випадку, якщо лівий бічний елемент у вузлі стає більшим за правий на будь-якому етапі, два елементи міняються місцями а потім проводяться подальші порівняння. Нарешті, кореневий вузол знову міститиме мінімальний елемент з лівого боку.
- Max елемент: В інтервальної купі максимальним елементом є елемент з правого боку від кореневого вузла. Цей елемент видаляється та повертається. Щоб заповнити вакансію, створену праворуч від кореневого вузла, елемент з останнього вузла видаляється і знову вставляється в кореневий вузол. Подальші порівняння проводяться на аналогічній основі, як описано вище. Нарешті, кореневий вузол знову міститиме max елемент з правого боку.
Таким чином, з інтервальними купами можна ефективно видаляти як мінімальні, так і максимальні елементи, переходячи від кореня до листків. Таким чином, можна отримати ДЧП з інтервальної купи, де елементи інтервальної купи є пріоритетами елементів у ДЧП.
Часова складність
Інтервальні купи
Коли ДЧП реалізовано з використанням Інтервальної купи, що складається з n елементів, часова складність для різних функцій буде рівною таким значенням:
| Функція | Часова складність |
|---|---|
| init( ) | O(n) |
| isEmpty( ) | O(1) |
| getmin( ) | O(1) |
| getmax( ) | O(1) |
| size( ) | O(1) |
| insert(x) | O(log n) |
| removeMin( ) | O(log n) |
| removeMax( ) | O(log n) |
Спряжені купи
Коли ДЧП реалізовано з використанням Спряженої купи, що складається з n елементів, часова складність для різних функцій буде рівною таким значенням: (Для спряжених куп складність є амортизованою.)
| Функція | Часова складність |
|---|---|
| isEmpty( ) | O(1) |
| getmin( ) | O(1) |
| getmax( ) | O(1) |
| insert(x) | O(log n) |
| removeMax( ) | O(log n) |
| removeMin( ) | O(log n) |
Застосування
Зовнішнє сортування
Одним із прикладів застосування двосторонньої черги з пріорітетністю є Зовнішнє сортування. При зовнішньому сортуванні кількість елементів, які сортуються, є більшою, ніж може поміститись в оперативній пам'яті комп'ютера. Процес сортування виконується і зберігається на диску. Зовнішнє швидке сортування реалізоване за допомогою ДЧП виглядає так:
- Прочитати і помістити в ДЧП стільки елементів на диску, скільки поміститься. Ці елементи стануть центральними(опорними).
- Продовжити читання тих елементів на диску, що залишились. Якщо наступний елемент ≤ найменшого елементу нашого ДЧП, то вивести його в лівій групі. Якщо ж наступний елемент ≥ найбільшого елементу нашого ДЧП - вивести його в правій групі. Інакше, вилучити з ДЧП найбільший чи найменший елемент(вибір може бути випадковий або визначений); якщо було вилучено найбільший елемент, то вивести його в правій групі; інакше, вивести вилучений елемент у лівій групі; прочитати і помістити новий елемент у ДЧП.
- Вивести посортовані центральні елементи ДЧП.
- Посортувати ліву і праву групи рекурсивно.
Див. також
Посилання
- Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues [ 20 січня 2022 у Wayback Machine.], , 1999.
- Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. с. 211. ISBN .
- . Архів оригіналу за 25 квітня 2012. Процитовано 4 жовтня 2011.
- . Архів оригіналу за 20 січня 2022. Процитовано 21 листопада 2021.
- Fundamentals of Data Structures in C++ - Ellis Horowitz, and Dinesh Mehta
- (PDF). Архів оригіналу (PDF) за 23 листопада 2018. Процитовано 21 листопада 2021.
{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
Джерела
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 6.5 Черги з пріоритетом. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ne plutati z Dvobichna cherga V komp yuternih naukah dvostoronnya cherga z prioritetom DChP abo zh dvostoronnya kupa ce struktura danih podibna do chergi z prioritetom chi kupi yaka dozvolyaye efektivno viluchati z neyi maksimalnij ta minimalnij element vidnosno prioritetu ob yektiv yaki znahodyatsya u cij strukturi Kozhen element u DChP maye svij prioritet i znachennya U DChP mozhlivo viluchati elementi yak u poryadku zrostannya tak i v poryadku spadannya FunkciyiDvostoronnya cherga z prioritetom dozvolyaye taki operaciyi isEmpty Pereviryaye chi DChP pusta i yaksho tak to povertaye znachennya True size Povertaye kilkist elementiv u danij DChP getMin Povertaye element z najnizhchim prioritetom getMax Povertaye element z najvishim prioritetom put x Dodaye element x do DChP removeMin Viluchaye element z najnizhchim prioritetom i povertaye jogo removeMax Viluchaye element z najvishim prioritetom i povertaye jogo Yaksho operaciya provoditsya nad dvoma elementami z odnakovoyu prioritetnistyu to bude vibrano toj yakij bulo dodano ranishe Takozh prioritet bud yakogo elementu mozhe buti zmineno pislya dodavannya jogo u DChP RealizaciyaDvostoronnya cherga z prioritetom mozhe buti stvorenoyu zi zbalansovanogo dvijkovogo dereva poshuku de elementi z najnizhchim i najvishim prioritetom ce krajnij livij i pravij listki vidpovidno abo vikoristovuyuchi taki specializovani strukturi danih yak en chi en Zagalnimi metodami otrimannya cherg iz dvostoronnim prioritetom iz zvichajnih prioritetnih cherg ye Metod podvijnoyi strukturi A dual structure with 14 12 4 10 8 as the members of DEPQ U comu metodi pidtrimuyutsya dvi chergi z riznimi prioritetami dlya min ta max Ti sami elementi v oboh prioritetnih chergah vidobrazhayutsya za dopomogoyu pokazhchikiv vidpovidnosti Tut minimalnij i maksimalnij elementi ye znachennyami sho mistyatsya v korenevih vuzlah minimalnoyi ta maksimalnoyi kupi vidpovidno Vidalennya elementa min Vikonajte removemin u minimalnij kupi ta remove znachennya vuzla u maksimalnij kupi de znachennya vuzla ce znachennya u vidpovidnomu vuzli v maksimalnij kupi Vidalennya elementa max Vikonajte removemax u maksimalnij kupi ta remove znachennya vuzla u minimalnij kupi de znachennya vuzla ce znachennya u vidpovidnomu vuzli minimalnoyi kupi Povna vidpovidnist A total correspondence heap for the elements 3 4 5 5 6 6 7 8 9 10 11 with element 11 as buffer Polovina elementiv znahoditsya v minimalnij prioritetnij cherci a insha polovina v maksimalnij prioritetnij cherzi Kozhen element u min PCh maye vidpovidnist odin do odnogo z elementom u max PCh Yaksho kilkist elementiv u DChP neparna odin iz elementiv zberigayetsya v buferi Prioritet kozhnogo elementa v minimalnij PCh bude menshim abo dorivnyuvatime vidpovidnomu elementu v maksimalnij PCh Listkova vidpovidnist A leaf correspondence heap for the same elements as above U comu metodi lishe listovi elementi min i max PCh utvoryuyut vidpovidni pari odin do odnogo Neobov yazkovo shob nelistkovi elementi buli v pari vidpovidnosti odin do odnogo Intervalni kupi Implementing a DEPQ using interval heap Okrim vishezgadanih metodiv vidpovidnosti DChP mozhna efektivno otrimati za dopomogoyu intervalnih kup Intervalna kupa shozha na vbudovanu en v yakij kozhen vuzol mistit dva elementi Ce povne dvijkove derevo u yakomu Livij element menshe abo dorivnyuye pravomu elementu Obidva elementi viznachayut zamknutij interval Interval predstavlenij bud yakim vuzlom krim korenevogo ye pidintervalom batkivskogo vuzla Elementi z livogo boku viznachayut min kupu Elementi z pravogo boku viznachayut max kupu Zalezhno vid kilkosti elementiv mozhlivi dva vipadki Parna kilkist elementiv U comu vipadku kozhen vuzol mistit dva elementi napriklad p ta q z p q Potim kozhen vuzol predstavlyayetsya intervalom p q Neparna kilkist elementiv U comu vipadku kozhen vuzol krim ostannogo mistit dva elementi predstavleni intervalom p q todi yak ostannij vuzol mistitime odin element i predstavlenij intervalom p p Vkladannya elementa Zalezhno vid kilkosti elementiv yaki vzhe prisutni v intervalnij kupi mozhlivi nastupni vipadki Neparna kilkist elementiv Yaksho kilkist elementiv u kupi intervaliv neparna novij element spochatku vstavlyayetsya v ostannij vuzol Potim vin poslidovno porivnyuyetsya z poperednimi elementami vuzla ta pereviryayetsya na vidpovidnist kriteriyam suttyevim dlya intervalnoyi kupi yak zaznacheno vishe U vipadku yaksho element ne zadovolnyaye zhoden z kriteriyiv jogo peremishuyut z ostannogo vuzla do korenya poki ne budut vikonani vsi umovi Parna kilkist elementiv Yaksho kilkist elementiv parna to dlya vstavki novogo elementa stvoryuyetsya dodatkovij vuzol Yaksho element potraplyaye livoruch vid batkivskogo intervalu vin vvazhayetsya v min kupi a yaksho element potraplyaye pravoruch vid batkivskogo intervalu vin rozglyadayetsya v max kupi Dali vin poslidovno porivnyuyetsya i peremishuyetsya vid ostannogo vuzla do korenya poki ne budut zadovoleni vsi umovi dlya intervalnoyi kupi Yaksho element znahoditsya v intervali samogo batkivskogo vuzla proces todi zupinyayetsya i peremishennya elementiv ne vidbuvayetsya Chas neobhidnij dlya vstavki elementa zalezhit vid kilkosti ruhiv neobhidnih dlya vikonannya vsih umov i ye O log n Viluchennya elementa Min element V intervalnoyi kupi minimalnim elementom ye element z livogo boku vid korenevogo vuzla Cej element vidalyayetsya ta povertayetsya Shob zapovniti vakansiyu stvorenu zliva vid korenevogo vuzla element z ostannogo vuzla vidalyayetsya i znovu vstavlyayetsya v korenevij vuzol Potim cej element poslidovno porivnyuyetsya z usima livimi elementami nizhidnih vuzliv i proces zupinyayetsya koli zadovolnyayutsya vsi umovi dlya intervalnoyi kupi U vipadku yaksho livij bichnij element u vuzli staye bilshim za pravij na bud yakomu etapi dva elementi minyayutsya miscyami a potim provodyatsya podalshi porivnyannya Nareshti korenevij vuzol znovu mistitime minimalnij element z livogo boku Max element V intervalnoyi kupi maksimalnim elementom ye element z pravogo boku vid korenevogo vuzla Cej element vidalyayetsya ta povertayetsya Shob zapovniti vakansiyu stvorenu pravoruch vid korenevogo vuzla element z ostannogo vuzla vidalyayetsya i znovu vstavlyayetsya v korenevij vuzol Podalshi porivnyannya provodyatsya na analogichnij osnovi yak opisano vishe Nareshti korenevij vuzol znovu mistitime max element z pravogo boku Takim chinom z intervalnimi kupami mozhna efektivno vidalyati yak minimalni tak i maksimalni elementi perehodyachi vid korenya do listkiv Takim chinom mozhna otrimati DChP z intervalnoyi kupi de elementi intervalnoyi kupi ye prioritetami elementiv u DChP Chasova skladnistIntervalni kupi Koli DChP realizovano z vikoristannyam Intervalnoyi kupi sho skladayetsya z n elementiv chasova skladnist dlya riznih funkcij bude rivnoyu takim znachennyam Funkciya Chasova skladnistinit O n isEmpty O 1 getmin O 1 getmax O 1 size O 1 insert x O log n removeMin O log n removeMax O log n Spryazheni kupi Koli DChP realizovano z vikoristannyam Spryazhenoyi kupi sho skladayetsya z n elementiv chasova skladnist dlya riznih funkcij bude rivnoyu takim znachennyam Dlya spryazhenih kup skladnist ye amortizovanoyu Funkciya Chasova skladnistisEmpty O 1 getmin O 1 getmax O 1 insert x O log n removeMax O log n removeMin O log n ZastosuvannyaZovnishnye sortuvannya Odnim iz prikladiv zastosuvannya dvostoronnoyi chergi z prioritetnistyu ye Zovnishnye sortuvannya Pri zovnishnomu sortuvanni kilkist elementiv yaki sortuyutsya ye bilshoyu nizh mozhe pomistitis v operativnij pam yati komp yutera Proces sortuvannya vikonuyetsya i zberigayetsya na disku Zovnishnye shvidke sortuvannya realizovane za dopomogoyu DChP viglyadaye tak Prochitati i pomistiti v DChP stilki elementiv na disku skilki pomistitsya Ci elementi stanut centralnimi opornimi Prodovzhiti chitannya tih elementiv na disku sho zalishilis Yaksho nastupnij element najmenshogo elementu nashogo DChP to vivesti jogo v livij grupi Yaksho zh nastupnij element najbilshogo elementu nashogo DChP vivesti jogo v pravij grupi Inakshe viluchiti z DChP najbilshij chi najmenshij element vibir mozhe buti vipadkovij abo viznachenij yaksho bulo vilucheno najbilshij element to vivesti jogo v pravij grupi inakshe vivesti viluchenij element u livij grupi prochitati i pomistiti novij element u DChP Vivesti posortovani centralni elementi DChP Posortuvati livu i pravu grupi rekursivno Div takozhCherga struktura danih Cherga z prioritetom Dvobichna chergaPosilannyaData Structures Algorithms amp Applications in Java Double Ended Priority Queues 20 sichnya 2022 u Wayback Machine 1999 Brass Peter 2008 Advanced Data Structures Cambridge University Press s 211 ISBN 9780521880374 Arhiv originalu za 25 kvitnya 2012 Procitovano 4 zhovtnya 2011 Arhiv originalu za 20 sichnya 2022 Procitovano 21 listopada 2021 Fundamentals of Data Structures in C Ellis Horowitz and Dinesh Mehta PDF Arhiv originalu PDF za 23 listopada 2018 Procitovano 21 listopada 2021 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite web title Shablon Cite web cite web a Obslugovuvannya CS1 Storinki z tekstom archived copy yak znachennya parametru title posilannya DzherelaT Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 6 5 Chergi z prioritetom Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4