Черга Бродала Тип Купа/Черга з пріоритетом Винайдено 1996 Винахідник Gerth Stølting Brodal Обчислювальна складність у O-нотації Операція Середнє Поганий випадок Просторова складність

У інформатиці черга Бродала — це структура даних типу купи/черги з пріоритетами з дуже малими часовими межами в найгіршому випадку: для вставлення, пошуку мінімуму, злиття (об’єднання двох черг) та зменшення ключа, і для видалення мінімуму та загального видалення. Це перший різновид купи, якому вдалося досягти цих меж без використання амортизації вартості операцій. Черги Бродала названі на честь їхнього винахідника — Герта Стольтінга Бродала.

Хоча вони мають кращі асимптотичні оцінки, ніж інші структури черг із пріоритетами, за словами самого Бродала, вони «доволі складні» і «[не] застосовні на практиці». Бродал і описують () версію черг Бродала.

Визначення Черга Бродала — це множина з двох дерев і та 5 guide-структур. Визначення структури даних guide наведено в наступному розділі. Для обох дерев кожен вузол має ранг, цей ранг корисний для подальших операцій і інтуїтивно відповідає логарифму розміру піддерева, вкоріненого в цьому вузлі. Позначимо кількість дітей вузла з рангом . Також використовуватимемо як корінь дерева , а як корінь дерева . У будь-який момент часу кожне піддерево, вкорінене в певному вузлі, має задовольняти ці 5 інваріантів (які далі називатимуться інваріантами ):

: Якщо це листок, тоді , : , : Якщо , тоді , : зазначимо, що , : або .

Тут гарантує нам, що розмір піддерева з коренем у вузлі є принаймні експоненціально залежним від рангу цього вузла. Крім того, обмежує кількість дітей кожного рангу для заданого вузла, це означає, що всі вузли мають ранг та степені в .

У черзі Бродала не кожен вузол матиме більше значення, ніж його батько; вузли, що порушують цю умову, називатимуться вузлами-порушниками. Однак ми хочемо, щоб кількість вузлів-порушників залишалася відносно малою. Щоб відстежувати вузли-порушники, для кожного вузла створюємо дві множини і вузлів, більших за . Інтуїтивно — це вузли, більші за , з великим рангом (тобто , якщо ), а — це вузли з малим рангом (). Ці множини реалізовано як двобічно зв’язані списки, тобто вони мають порядок. Зокрема, усі вузли-порушники, додані до , додаються на початок списку, а всі вузли-порушники, додані до , вставляються поруч із вузлом того самого рангу. Нехай позначає кількість вузлів у рангу . Списки і задовольняють ці 5 інваріантів (далі називатимемо їх інваріантами):

: Якщо тоді : Якщо тоді існує вузол такий що

: Позначивши , ми маємо: for певна константа .

Оскільки всі вузли мають ранг у , то з інваріантів і випливає, що всі та мають розмір .

У нас також є деякі інваріанти коренів дерев і : і (так званий інваріанти).

: , : , : if , тоді .

Інваріант по суті каже нам, що якщо ми збільшимо ранг на одиницю, то матимемо щонайбільше нових «великих» порушень (тут «великі» означає з високим рангом), не порушуючи інваріант . З іншого боку, інваріант повідомляє, що всі порушення в є «малими»; цей інваріант істинний за означенням . Підтримувати інваріант і нетривіально; щоб підтримувати їх, ми використаємо операцію , яку можна реалізувати за допомогою guide, визначеного в наступному розділі. Щоразу, коли ми викликатимемо операцію , ми по суті:

Структура даних guide Це визначення базується на визначенні зі статті Бродала.

Припустимо, що маємо послідовність змінних і хочемо гарантувати, що для деякого порога . Єдина дозволена операція — , яка зменшує щонайменше на 2 та збільшує щонайбільше на 1. Без втрати загальності можна вважати, що зменшує на 2 і збільшує на 1.

Якщо деяке збільшується на одиницю, мета guide — підказати, для яких індексів і слід застосувати , щоб не порушити поріг. Guide дозволено робити лише викликів функції для кожного такого збільшення.

Guide має доступ до іншої послідовності такої, що і . Поки після збільшення маємо , нам не потрібно звертатися по допомогу до guide, оскільки «далеко» нижче за . Однак якщо перед збільшенням , то після зміни матимемо .

Щоб спростити пояснення, можна припустити, що , тоді . Guide створюватиме блоки в послідовності вигляду , причому допускається, що може не бути взагалі. Guide підтримує інваріант: кожен елемент, який не входить до блоку, є або , або . Наприклад, ось блоки для послідовності .

Guide складається з трьох масивів:

масив з масив з масив вказівників, у якому всі , для яких відповідні перебувають в одному блоці, вказують на одну й ту саму комірку пам’яті, що містить значення. Якщо деяке не належить до жодного блоку, тоді вказує на комірку пам’яті, що містить значення .

За таким означенням guide має дві важливі властивості:

Для кожного елемента в блоці ми можемо знайти найлівіший елемент блоку за часом . Ми можемо вчасно зруйнувати блок шляхом призначення до комірки пам'яті, на яку вказує кожен елемент блоку.

Таким чином guide може визначати, які індекси потрібно застосувати до , за час . Ось приклад:

Щоб відновити блоки, вказівники елементів 1 і 0, доданих до першого блоку, тепер вказують на ту саму комірку, що й усі інші елементи першого блоку, а значення комірки другого блоку змінюється на . У попередньому прикладі було потрібно лише дві операції ; насправді так відбувається в усіх випадках. Отже, черзі потрібно лише операцій, щоб відновити цю властивість.

Операції черги Бродала Щоб реалізувати операції з чергами з різними пріоритетами, нам спочатку потрібно описати деякі важливі перетворення для дерев.

Трансформації

Зв'язування дерев Щоб зв'язати дерева, нам потрібні три вузли однакового рангу. Ми можемо обчислити мінімум цих трьох вузлів за допомогою двох порівнянь. Тут ми припускаємо, що є мінімальним, але процес однаковий для всіх Тепер ми можемо зробити вузли і двох крайніх лівих синів та підвищити ранг на один. Це зберігає всі і інваріанти.

Роз'єднання дерев Якщо має рівно двох чи трьох синів за рангом , ми можемо видалити цих синів і отримує ранг свого нового найбільшого сина плюс один. Від умова, ми знаємо, що інваріант буде збережено. Тоді всі і інваріанти залишаються виконаними. Якщо має 4 або більше дітей, ми можемо просто вирізати двох з них, і всі інваріанти залишаться істинними. Отже, роз'єднання дерева рангів завжди призведе до двох або трьох дерев рангу (з 2 або 3 відрізаних дітей) та максимум одне додаткове дерево рангу .

Збереження синів кореня Коли ми додаємо та видаляємо синів кореня, ми хочемо зберегти інваріант істинний. Для цього ми використовуємо 4 guide, по два для кожного кореня і Мати постійний доступ до сина ми створюємо розширюваний масив pointed, який для кожного рангу має вказівник на сина рангу . Один guide підтримуватиме умову, що ⁣, а інший підтримує як для Сини рангу і розглядаються окремо простим способом, щоб їхня кількість залишалася від 2 до 7. Еквівалент змінна у визначенні guide матиме значення для верхньої межі guide та для нижньої межі.

⁣У цьому контексті, коли ми додаємо дочірній елемент рангу до кореня, ми збільшуємо на один, і застосуйте операції. операція тут полягає у зв'язуванні трьох дерев рангу що створює нову дитину рангу Отже, ми зменшуємо на три та збільшити на один. Якщо це збільшення призведе до появи занадто великої кількості синів рангу або ми пов'язуємо деяких із цих синів разом і, можливо, підвищуємо ранг Якщо ми підвищимо ранг , нам потрібно збільшити довжину розширюваного масиву, яким керують guide.

Відрізати сина від дуже схоже, за винятком того, що тут Операція відповідає роз'єднанню дерева.

Для кореня ситуація майже така ж. Однак, оскільки гарантує нам, що є мінімальним елементом, ми знаємо, що не створимо жодних порушень, пов'язуючи або видаляючи зв'язки з дочірніми елементами Цього ж не можна сказати про Зв'язування синів ніколи не створить нових порушень, але роз'єднання синів може створити до трьох нових порушень. Дерево, що залишається в результаті роз'єднання, стає сином якщо його ранг менший за ⁣, інакше воно стає сином Нові порушення, які мають рейтинг більший за додаються до , Щоб зберегти інваріанти на набір (а саме і ), ми повинні гарантувати, що ранг буде збільшено, і це у цих інваріантах вибирається достатньо великим.

Зменшення порушень Мета цієї трансформації полягає у зменшенні загальної кількості потенційних порушень, тобто зменшення .

Ми припускаємо, що маємо два потенційних порушення і рівного рангу Тоді маємо кілька випадків:

Якщо виявиться, що один із вузлів не є вузлом-порушником, ми просто вилучаємо його з відповідної множини порушень. Інакше обидва вузли є вузлами-порушниками. Через ми знаємо, що і , і мають принаймні одного брата. Тоді: Якщо і не є братами, то без втрати загальності можна припустити, що ; тоді можна поміняти місцями піддерева, вкорінені в та . Під час такої перестановки кількість порушень може лише зменшитися. Інакше і є братами, а їхнього батьківського вузла позначимо як . Якщо має більше ніж одного брата рангу , ми можемо просто від’єднати і зробити його вузлом без порушення, як описано в попередньому підрозділі. Інакше, та єдині діти рангу вузла : Якщо , ми можемо від’єднати від обидва вузли і та зробити їх вузлами без порушення, як описано в попередньому підрозділі. Else, . We will cut off , the new rank of will be one plus the rank of its leftmost son, We replace by a son on of rank , which can be cut off as described in the previous subsection. If the replacement for becomes a violating node of rank , we add it to . Finally we make new sons of as described above.

Уникнення надмірної кількості порушень Єдині набори порушень, куди ми додамо порушення, це і Як описано вище, інваріанти на цих множинах підтримуються за допомогою guide. Коли ми додаємо порушення до маємо два випадки:

Якщо є рівно 6 порушень заданого рангу і є принаймні два вузли-порушники, які не є синами , ми застосовуємо операції, надані посібником. Якщо є понад 4 порушень, які є синами , ми вирізаємо додаткові порушення та надаємо посилання на них нижче Це усуває порушення, створене цими вузлами, і не впливає на те, як guide підтримує синів .

Для кожної виконаної операції з пріоритетною чергою ми збільшуємо ранг принаймні одним шляхом переміщення постійної кількості синів до (за умови, що ). Підвищення рангу дозволяє нам додавати порушення до зберігаючи при цьому всі наші інваріанти. Якщо і ми можемо вирізати найбільших синів , зв’яжіть їх з ⁣, а потім зробити син Це задовольняє всі інваріанти. В іншому випадку ми відсікаємо сина рангу , роз’єднайте цього сина та додайте отримані дерева до Якщо , ми знаємо, що є вузлом найбільшого рангу, тому ми знаємо, що великих порушень створювати не можна.

Операції з пріоритетною чергою

MakeQueue просто повертає пару порожніх дерев.

FindMin повертає .

Insert є лише особливим випадком де є чергою, що містить тільки та .

Meld включає чотири дерева (по два для кожної черги). Дерево з мінімальним коренем стає новим деревом. Якщо це дерево також є деревом максимального рангу, ми можемо додати всі інші дерева нижче, як описано раніше. У цьому випадку не створюється жоден вузол, що порушує правила, тому перетворення на вузлах, що порушують правила, не виконується. В іншому випадку дерево максимального рангу стає новим дерево та інші дерева додаються нижче, як описано в розділі «Збереження синів кореня». Якщо деякі дерева мають рівний ранг з цим новим , ми можемо від'єднати їх перед додаванням. Створені порушення обробляються, як описано в розділі: «Уникнення надмірної кількості порушень».

DecreaseKey замінює елемент на (де ). Якщо , ми обмінюємося двома вузлами, інакше ми обробляємо потенційне нове порушення, як пояснено в розділі "Уникнення надмірної кількості порушень".

DeleteMin