Двостороння черга з пріоритетом
В комп'ютерних науках, двостороння черга з пріоритетом (ДЧП)[1] або ж двостороння купа[2] це структура даних подібна до черги з пріорітетом чи купи, яка дозволяє ефективно вилучати з неї максимальний та мінімальний елемент відносно пріорітету об'єктів, які знаходяться у цій структурі. Кожен елемент у ДЧП має свій пріорітет і значення. У ДЧП можливо вилучати елементи як у порядку зростання, так і в порядку спадання.[3]
Двостороння черга з пріоритетом дозволяє такі операції:
- isEmpty()
- Перевіряє, чи ДЧП пуста і, якщо так, то повертає значення True.
- size()
- Повертає кількість елементів у даній ДЧП.
- getMin()
- Повертає елемент з найнижчим пріорітетом.
- getMax()
- Повертає елемент з найвищим пріорітетом.
- put(x)
- Додає елемент x до ДЧП.
- removeMin()
- Вилучає елемент з найнижчим пріорітетом і повертає його.
- removeMax()
- Вилучає елемент з найвищим пріорітетом і повертає його.
Якщо операція проводиться над двома елементами з однаковою пріорітетністю, то буде вибрано той, який було додано раніше. Також, пріоритет будь-якого елементу може бути змінено після додавання його у ДЧП.[4]
Двостороння черга з пріоритетом може бути створеною зі збалансованого двійкового дерева пошуку (де елементи з найнижчим і найвищим пріорітетом це крайній лівий і правий листки відповідно), або використовуючи такі спеціалізовані структури даних, як мін-макс купи[en] чи спряженої купи[en].
Загальними методами отримання черг із двостороннім пріоритетом із звичайних пріоритетних черг є:[5]
У цьому методі підтримуються дві черги з різними пріоритетами для min та max. Ті самі елементи в обох пріорітетних чергах відображаються за допомогою покажчиків відповідності. Тут мінімальний і максимальний елементи є значеннями, що містяться в кореневих вузлах мінімальної та максимальної купи відповідно.
- Видалення елемента min: Виконайте removemin() у мінімальній купі та remove(значення вузла) у максимальній купі, де значення вузла – це значення у відповідному вузлі в максимальній купі.
- Видалення елемента max: Виконайте removemax() у максимальній купі та remove(значення вузла) у мінімальній купі, де значення вузла – це значення у відповідному вузлі мінімальної купі.
Половина елементів знаходиться в мінімальній пріоритетній черці, а інша половина в максимальній пріорітетній черзі. Кожен елемент у min ПЧ має відповідність один до одного з елементом у max ПЧ. Якщо кількість елементів у ДЧП непарна, один із елементів зберігається в буфері.[1] Пріоритет кожного елемента в мінімальній ПЧ буде меншим або дорівнюватиме відповідному елементу в максимальній ПЧ.
У цьому методі лише листові елементи min і max ПЧ утворюють відповідні пари один до одного. Необов’язково, щоб нелисткові елементи були в парі відповідності один до одного.[1]
Окрім вищезгаданих методів відповідності, ДЧП можна ефективно отримати за допомогою інтервальних куп.[6] Інтервальна купа схожа на вбудовану мін-макс купу[en], в якій кожен вузол містить два елементи. Це повне двійкове дерево, у якому:[6]
- Лівий елемент менше або дорівнює правому елементу.
- Обидва елементи визначають замкнутий інтервал.
- Інтервал, представлений будь-яким вузлом, крім кореневого, є підінтервалом батьківського вузла.
- Елементи з лівого боку визначають min купу.
- Елементи з правого боку визначають max купу.
Залежно від кількості елементів можливі два випадки[6] -
- Парна кількість елементів: У цьому випадку кожен вузол містить два елементи, наприклад, p та q, з p ≤ q. Потім кожен вузол представляється інтервалом [p, q].
- Непарна кількість елементів: У цьому випадку кожен вузол, крім останнього, містить два елементи, представлені інтервалом [p, q], тоді як останній вузол міститиме один елемент і представлений інтервалом [p, p].
Залежно від кількості елементів, які вже присутні в інтервальній купі, можливі наступні випадки:
- Непарна кількість елементів: Якщо кількість елементів у купі інтервалів непарна, новий елемент спочатку вставляється в останній вузол. Потім він послідовно порівнюється з попередніми елементами вузла та перевіряється на відповідність критеріям, суттєвим для інтервальної купи, як зазначено вище. У випадку, якщо елемент не задовольняє жоден з критеріїв, його переміщують з останнього вузла до кореня, поки не будуть виконані всі умови.[6]
- Парна кількість елементів: Якщо кількість елементів парна, то для вставки нового елемента створюється додатковий вузол. Якщо елемент потрапляє ліворуч від батьківського інтервалу, він вважається в min купі, а якщо елемент потрапляє праворуч від батьківського інтервалу, він розглядається в max купі. Далі він послідовно порівнюється і переміщується від останнього вузла до кореня, поки не будуть задоволені всі умови для інтервальної купи. Якщо елемент знаходиться в інтервалі самого батьківського вузла, процес тоді зупиняється і переміщення елементів не відбувається.[6]
Час, необхідний для вставки елемента, залежить від кількості рухів, необхідних для виконання всіх умов і є O(log n).
- Min елемент: В інтервальної купі мінімальним елементом є елемент з лівого боку від кореневого вузла. Цей елемент видаляється та повертається. Щоб заповнити вакансію, створену зліва від кореневого вузла, елемент з останнього вузла видаляється і знову вставляється в кореневий вузол. Потім цей елемент послідовно порівнюється з усіма лівими елементами низхідних вузлів, і процес зупиняється, коли задовольняються всі умови для інтервальної купи. У випадку, якщо лівий бічний елемент у вузлі стає більшим за правий на будь-якому етапі, два елементи міняються місцями[6] а потім проводяться подальші порівняння. Нарешті, кореневий вузол знову міститиме мінімальний елемент з лівого боку.
- Max елемент: В інтервальної купі максимальним елементом є елемент з правого боку від кореневого вузла. Цей елемент видаляється та повертається. Щоб заповнити вакансію, створену праворуч від кореневого вузла, елемент з останнього вузла видаляється і знову вставляється в кореневий вузол. Подальші порівняння проводяться на аналогічній основі, як описано вище. Нарешті, кореневий вузол знову міститиме max елемент з правого боку.
Таким чином, з інтервальними купами можна ефективно видаляти як мінімальні, так і максимальні елементи, переходячи від кореня до листків. Таким чином, можна отримати ДЧП[6] з інтервальної купи, де елементи інтервальної купи є пріоритетами елементів у ДЧП.
Коли ДЧП реалізовано з використанням Інтервальної купи, що складається з n елементів, часова складність для різних функцій буде рівною таким значенням:[1]
| Функція | Часова складність |
|---|---|
| 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 елементів, часова складність для різних функцій буде рівною таким значенням:[1] (Для спряжених куп складність є амортизованою.)
| Функція | Часова складність |
|---|---|
| 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.], Sartaj Sahni, 1999.
- ↑ Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. с. 211. ISBN 9780521880374.
- ↑ Depq - Double-Ended Priority Queue. Архів оригіналу за 25 квітня 2012. Процитовано 4 жовтня 2011.
- ↑ depq. Архів оригіналу за 20 січня 2022. Процитовано 21 листопада 2021.
- ↑ Fundamentals of Data Structures in C++ - Ellis Horowitz, Sartaj Sahni and Dinesh Mehta
- ↑ а б в г д е ж Архівована копія (PDF). Архів оригіналу (PDF) за 23 листопада 2018. Процитовано 21 листопада 2021.
{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 6.5 Черги з пріоритетом. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.