В комп'ютерних науках, двостороння черга з пріоритетом (ДЧП)[1] або ж двостороння купа[2] це структура даних подібна до черги з пріорітетом чи купи, яка дозволяє ефективно вилучати з неї максимальний та мінімальний елемент відносно пріорітету об'єктів, які знаходяться у цій структурі. Кожен елемент у ДЧП має свій пріорітет і значення. У ДЧП можливо вилучати елементи як у порядку зростання, так і в порядку спадання.[3]
Функції
Двостороння черга з пріоритетом дозволяє такі операції:
isEmpty()
Перевіряє, чи ДЧП пуста і, якщо так, то повертає значення True.
size()
Повертає кількість елементів у даній ДЧП.
getMin()
Повертає елемент з найнижчим пріорітетом.
getMax()
Повертає елемент з найвищим пріорітетом.
put(x)
Додає елемент x до ДЧП.
removeMin()
Вилучає елемент з найнижчим пріорітетом і повертає його.
removeMax()
Вилучає елемент з найвищим пріорітетом і повертає його.
Якщо операція проводиться над двома елементами з однаковою пріорітетністю, то буде вибрано той, який було додано раніше. Також, пріоритет будь-якого елементу може бути змінено після додавання його у ДЧП.[4]
Загальними методами отримання черг із двостороннім пріоритетом із звичайних пріоритетних черг є:[5]
Метод подвійної структури
A dual structure with 14,12,4,10,8 as the members of DEPQ.[1]
У цьому методі підтримуються дві черги з різними пріоритетами для min та max. Ті самі елементи в обох пріорітетних чергах відображаються за допомогою покажчиків відповідності. Тут мінімальний і максимальний елементи є значеннями, що містяться в кореневих вузлах мінімальної та максимальної купи відповідно.
Видалення елемента min: Виконайте removemin() у мінімальній купі та remove(значення вузла) у максимальній купі, де значення вузла – це значення у відповідному вузлі в максимальній купі.
Видалення елемента max: Виконайте removemax() у максимальній купі та remove(значення вузла) у мінімальній купі, де значення вузла – це значення у відповідному вузлі мінімальної купі.
Повна відповідність
A total correspondence heap for the elements 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11 with element 11 as buffer.[1]
Половина елементів знаходиться в мінімальній пріоритетній черці, а інша половина в максимальній пріорітетній черзі. Кожен елемент у min ПЧ має відповідність один до одного з елементом у max ПЧ. Якщо кількість елементів у ДЧП непарна, один із елементів зберігається в буфері.[1] Пріоритет кожного елемента в мінімальній ПЧ буде меншим або дорівнюватиме відповідному елементу в максимальній ПЧ.
Листкова відповідність
A leaf correspondence heap for the same elements as above.[1]
У цьому методі лише листові елементи min і max ПЧ утворюють відповідні пари один до одного. Необов’язково, щоб нелисткові елементи були в парі відповідності один до одного.[1]
Інтервальні купи
Implementing a DEPQ using interval heap.
Окрім вищезгаданих методів відповідності, ДЧП можна ефективно отримати за допомогою інтервальних куп.[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)
Застосування
Зовнішнє сортування
Одним із прикладів застосування двосторонньої черги з пріорітетністю є Зовнішнє сортування. При зовнішньому сортуванні кількість елементів, які сортуються, є більшою, ніж може поміститись в оперативній пам'яті комп'ютера. Процес сортування виконується і зберігається на диску. Зовнішнє швидке сортування реалізоване за допомогою ДЧП виглядає так:
Прочитати і помістити в ДЧП стільки елементів на диску, скільки поміститься. Ці елементи стануть центральними(опорними).
Продовжити читання тих елементів на диску, що залишились. Якщо наступний елемент ≤ найменшого елементу нашого ДЧП, то вивести його в лівій групі. Якщо ж наступний елемент ≥ найбільшого елементу нашого ДЧП - вивести його в правій групі. Інакше, вилучити з ДЧП найбільший чи найменший елемент(вибір може бути випадковий або визначений); якщо було вилучено найбільший елемент, то вивести його в правій групі; інакше, вивести вилучений елемент у лівій групі; прочитати і помістити новий елемент у ДЧП.
↑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 (посилання)
