В комп'ютерних науках, двостороння черга з пріоритетом (ДЧП)Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues , Sartaj Sahni, 1999. або ж двостороння купа це структура даних подібна до черги з пріорітетом чи купи, яка дозволяє ефективно вилучати з неї максимальний та мінімальний елемент відносно пріорітету об'єктів, які знаходяться у цій структурі. Кожен елемент у ДЧП має свій пріорітет і значення. У ДЧП можливо вилучати елементи як у порядку зростання, так і в порядку спадання.
Функції Двостороння черга з пріоритетом дозволяє такі операції:
isEmpty() Перевіряє, чи ДЧП пуста і, якщо так, то повертає значення True. size() Повертає кількість елементів у даній ДЧП. getMin() Повертає елемент з найнижчим пріорітетом. getMax() Повертає елемент з найвищим пріорітетом. put(x) Додає елемент x до ДЧП. removeMin() Вилучає елемент з найнижчим пріорітетом і повертає його. removeMax() Вилучає елемент з найвищим пріорітетом і повертає його.
Якщо операція проводиться над двома елементами з однаковою пріорітетністю, то буде вибрано той, який було додано раніше. Також, пріоритет будь-якого елементу може бути змінено після додавання його у ДЧП.
Реалізація Двостороння черга з пріоритетом може бути створеною зі збалансованого двійкового дерева пошуку (де елементи з найнижчим і найвищим пріорітетом це крайній лівий і правий листки відповідно), або використовуючи такі спеціалізовані структури даних, як чи .
Загальними методами отримання черг із двостороннім пріоритетом із звичайних пріоритетних черг є:Fundamentals of Data Structures in C++ - Ellis Horowitz, Sartaj Sahni and Dinesh Mehta
Метод подвійної структури
У цьому методі підтримуються дві черги з різними пріоритетами для min та max. Ті самі елементи в обох пріорітетних чергах відображаються за допомогою покажчиків відповідності. Тут мінімальний і максимальний елементи є значеннями, що містяться в кореневих вузлах мінімальної та максимальної купи відповідно.
Видалення елемента min: Виконайте removemin() у мінімальній купі та remove(значення вузла) у максимальній купі, де значення вузла – це значення у відповідному вузлі в максимальній купі. Видалення елемента max: Виконайте removemax() у максимальній купі та remove(значення вузла) у мінімальній купі, де значення вузла – це значення у відповідному вузлі мінімальної купі.
Повна відповідність
Половина елементів знаходиться в мінімальній пріоритетній черці, а інша половина в максимальній пріорітетній черзі. Кожен елемент у min ПЧ має відповідність один до одного з елементом у max ПЧ. Якщо кількість елементів у ДЧП непарна, один із елементів зберігається в буфері. Пріоритет кожного елемента в мінімальній ПЧ буде меншим або дорівнюватиме відповідному елементу в максимальній ПЧ.
Листкова відповідність
У цьому методі лише листові елементи min і max ПЧ утворюють відповідні пари один до одного. Необов’язково, щоб нелисткові елементи були в парі відповідності один до одного.
Інтервальні купи
Окрім вищезгаданих методів відповідності, ДЧП можна ефективно отримати за допомогою інтервальних куп. Інтервальна купа схожа на вбудовану , в якій кожен вузол містить два елементи. Це повне двійкове дерево, у якому:
Лівий елемент менше або дорівнює правому елементу. Обидва елементи визначають замкнутий інтервал. Інтервал, представлений будь-яким вузлом, крім кореневого, є підінтервалом батьківського вузла. Елементи з лівого боку визначають 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)
Застосування
Зовнішнє сортування Одним із прикладів застосування двосторонньої черги з пріорітетністю є Зовнішнє сортування. При зовнішньому сортуванні кількість елементів, які сортуються, є більшою, ніж може поміститись в оперативній пам'яті комп'ютера. Процес сортування виконується і зберігається на диску. Зовнішнє швидке сортування реалізоване за допомогою ДЧП виглядає так:
Прочитати і помістити в ДЧП стільки елементів на диску, скільки поміститься. Ці елементи стануть центральними(опорними). Продовжити читання тих елементів на диску, що залишились. Якщо наступний елемент ≤ найменшого елементу нашого ДЧП, то вивести його в лівій групі. Якщо ж наступний елемент ≥ найбільшого елементу нашого ДЧП - вивести його в правій групі. Інакше, вилучити з ДЧП найбільший чи найменший елемент(вибір може бути випадковий або визначений); якщо було вилучено найбільший елемент, то вивести його в правій групі; інакше, вивести вилучений елемент у лівій групі; прочитати і помістити новий елемент у ДЧП. Вивести посортовані центральні елементи ДЧП. Посортувати ліву і праву групи рекурсивно.
Див. також
Черга (структура даних) Черга з пріоритетом Двобічна черга
Посилання
Джерела