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

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] Інтервальна купа схожа на вбудовану мін-макс купу, в якій кожен вузол містить два елементи. Це повне двійкове дерево, у якому:[6]

• Лівий елемент менше або дорівнює правому елементу.
• Обидва елементи визначають замкнутий інтервал.
• Інтервал, представлений будь-яким вузлом, крім кореневого, є підінтервалом батьківського вузла.
• Елементи з лівого боку визначають min купу.
• Елементи з правого боку визначають max купу.

Залежно від кількості елементів можливі два випадки[6] -

1. Парна кількість елементів: У цьому випадку кожен вузол містить два елементи, наприклад, p та q, з p ≤ q. Потім кожен вузол представляється інтервалом [p, q].
2. Непарна кількість елементів: У цьому випадку кожен вузол, крім останнього, містить два елементи, представлені інтервалом [p, q], тоді як останній вузол міститиме один елемент і представлений інтервалом [p, p].

Залежно від кількості елементів, які вже присутні в інтервальній купі, можливі наступні випадки:

• Непарна кількість елементів: Якщо кількість елементів у купі інтервалів непарна, новий елемент спочатку вставляється в останній вузол. Потім він послідовно порівнюється з попередніми елементами вузла та перевіряється на відповідність критеріям, суттєвим для інтервальної купи, як зазначено вище. У випадку, якщо елемент не задовольняє жоден з критеріїв, його переміщують з останнього вузла до кореня, поки не будуть виконані всі умови.[6]
• Парна кількість елементів: Якщо кількість елементів парна, то для вставки нового елемента створюється додатковий вузол. Якщо елемент потрапляє ліворуч від батьківського інтервалу, він вважається в min купі, а якщо елемент потрапляє праворуч від батьківського інтервалу, він розглядається в max купі. Далі він послідовно порівнюється і переміщується від останнього вузла до кореня, поки не будуть задоволені всі умови для інтервальної купи. Якщо елемент знаходиться в інтервалі самого батьківського вузла, процес тоді зупиняється і переміщення елементів не відбувається.[6]

Час, необхідний для вставки елемента, залежить від кількості рухів, необхідних для виконання всіх умов і є O(log n).

• Min елемент: В інтервальної купі мінімальним елементом є елемент з лівого боку від кореневого вузла. Цей елемент видаляється та повертається. Щоб заповнити вакансію, створену зліва від кореневого вузла, елемент з останнього вузла видаляється і знову вставляється в кореневий вузол. Потім цей елемент послідовно порівнюється з усіма лівими елементами низхідних вузлів, і процес зупиняється, коли задовольняються всі умови для інтервальної купи. У випадку, якщо лівий бічний елемент у вузлі стає більшим за правий на будь-якому етапі, два елементи міняються місцями[6] а потім проводяться подальші порівняння. Нарешті, кореневий вузол знову міститиме мінімальний елемент з лівого боку.
• Max елемент: В інтервальної купі максимальним елементом є елемент з правого боку від кореневого вузла. Цей елемент видаляється та повертається. Щоб заповнити вакансію, створену праворуч від кореневого вузла, елемент з останнього вузла видаляється і знову вставляється в кореневий вузол. Подальші порівняння проводяться на аналогічній основі, як описано вище. Нарешті, кореневий вузол знову міститиме max елемент з правого боку.

Таким чином, з інтервальними купами можна ефективно видаляти як мінімальні, так і максимальні елементи, переходячи від кореня до листків. Таким чином, можна отримати ДЧП[6] з інтервальної купи, де елементи інтервальної купи є пріоритетами елементів у ДЧП.

Коли ДЧП реалізовано з використанням Інтервальної купи, що складається з n елементів, часова складність для різних функцій буде рівною таким значенням:[1]

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

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

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