Двостороння черга з пріоритетом

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

В комп'ютерних науках, двостороння черга з пріоритетом (ДЧП)[1] або ж двостороння купа[2] це структура даних подібна до черги з пріорітетом чи купи, яка дозволяє ефективно вилучати з неї максимальний та мінімальний елемент відносно пріорітету об'єктів, які знаходяться у цій структурі. Кожен елемент у ДЧП має свій пріорітет і значення. У ДЧП можливо вилучати елементи як у порядку зростання, так і в порядку спадання.[3]

Функції

[ред. | ред. код]

Двостороння черга з пріоритетом дозволяє такі операції:

isEmpty()
Перевіряє, чи ДЧП пуста і, якщо так, то повертає значення True.
size()
Повертає кількість елементів у даній ДЧП.
getMin()
Повертає елемент з найнижчим пріорітетом.
getMax()
Повертає елемент з найвищим пріорітетом.
put(x)
Додає елемент x до ДЧП.
removeMin()
Вилучає елемент з найнижчим пріорітетом і повертає його.
removeMax()
Вилучає елемент з найвищим пріорітетом і повертає його.

Якщо операція проводиться над двома елементами з однаковою пріорітетністю, то буде вибрано той, який було додано раніше. Також, пріоритет будь-якого елементу може бути змінено після додавання його у ДЧП.[4]

Реалізація

[ред. | ред. код]

Двостороння черга з пріоритетом може бути створеною зі збалансованого двійкового дерева пошуку (де елементи з найнижчим і найвищим пріорітетом це крайній лівий і правий листки відповідно), або використовуючи такі спеціалізовані структури даних, як мін-макс купи[en] чи спряженої купи[en].

Загальними методами отримання черг із двостороннім пріоритетом із звичайних пріоритетних черг є:[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] -

  1. Парна кількість елементів: У цьому випадку кожен вузол містить два елементи, наприклад, p та q, з pq. Потім кожен вузол представляється інтервалом [p, q].
  2. Непарна кількість елементів: У цьому випадку кожен вузол, крім останнього, містить два елементи, представлені інтервалом [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)

Застосування

[ред. | ред. код]

Зовнішнє сортування

[ред. | ред. код]

Одним із прикладів застосування двосторонньої черги з пріорітетністю є Зовнішнє сортування. При зовнішньому сортуванні кількість елементів, які сортуються, є більшою, ніж може поміститись в оперативній пам'яті комп'ютера. Процес сортування виконується і зберігається на диску. Зовнішнє швидке сортування реалізоване за допомогою ДЧП виглядає так:

  1. Прочитати і помістити в ДЧП стільки елементів на диску, скільки поміститься. Ці елементи стануть центральними(опорними).
  2. Продовжити читання тих елементів на диску, що залишились. Якщо наступний елемент ≤ найменшого елементу нашого ДЧП, то вивести його в лівій групі. Якщо ж наступний елемент ≥ найбільшого елементу нашого ДЧП - вивести його в правій групі. Інакше, вилучити з ДЧП найбільший чи найменший елемент(вибір може бути випадковий або визначений); якщо було вилучено найбільший елемент, то вивести його в правій групі; інакше, вивести вилучений елемент у лівій групі; прочитати і помістити новий елемент у ДЧП.
  3. Вивести посортовані центральні елементи ДЧП.
  4. Посортувати ліву і праву групи рекурсивно.

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]
  1. а б в г д е ж и Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues [Архівовано 20 січня 2022 у Wayback Machine.], Sartaj Sahni, 1999.
  2. Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. с. 211. ISBN 9780521880374.
  3. Depq - Double-Ended Priority Queue. Архів оригіналу за 25 квітня 2012. Процитовано 4 жовтня 2011.
  4. depq. Архів оригіналу за 20 січня 2022. Процитовано 21 листопада 2021.
  5. Fundamentals of Data Structures in C++ - Ellis Horowitz, Sartaj Sahni and Dinesh Mehta
  6. а б в г д е ж Архівована копія (PDF). Архів оригіналу (PDF) за 23 листопада 2018. Процитовано 21 листопада 2021.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)

Джерела

[ред. | ред. код]