клас Queue
Збалансоване бінарне дерево дозволяє швидко знайти будь-який вузол. Однак у багатьох додатках потрібно отримувати не довільний вузол, а тільки мінімальний. Таке завдання виникає, наприклад, при організації спрямованого пошуку. Підходящої для цього структурою даних буде пріоритетна чергу (priority queue).
Перш ніж обговорювати деталі організації пріоритетною черзі, наведемо приклад її використання (модуль queue.js): У цьому прикладі в пріоритетну чергу послідовно поміщається 50 випадкових чисел в діапазоні від 0 до 99. Потім в циклі while елементи з черги виштовхуються в порядку збільшення їх значення :
Крім конструктора, в класі Queue є 3 базові функції: unshift (n) - додавання в чергу нового елемента n (зрушуючи "назад" великі елементи), shift () - виштовхування мінімального елемента (зрушуючи чергу "вперед") і, нарешті, логічна функція empty () повертає true. якщо чергу порожня (інакше - false).
У пріоритетною черзі можна зберігати не тільки числа або рядки, а й будь-які об'єкти. Для цього необхідно перевизначити функцію менше:
Організація дерева черзі
Впорядкуємо вузли пріоритетною черзі у вигляді бінарного дерева. У цього дерева два нащадка кожного вузла повинні бути великими або рівними батьківського вузла. Відповідно, в корені дерева знаходиться найменший вузол. Така організація пріоритетною черзі називається двійковій купою. Нижче наведено дерево черзі випадкових чисел з першого прикладу попереднього розділу:
Вузли дерева будемо зберігати в масиві ar. Кореневої вузол знаходиться в елементі ar [1]. Його два нащадка в ar [2] і ar [3]. Нащадки i-того вузла (елемента ar [i]) зберігаються в ar [2 * i] і ar [2 * i + 1]. Завдяки такій організації даних, бінарне дерево максимально збалансовано. Якщо число вузлів одно length = 2 k -1. то в дереві будуть зайняті всі листя на його нижньому (k -тому) рівні. У загальному випадку, нижній рівень дерева заповнюється зліва направо і в ar [length] знаходиться самий правий вузол нижнього рівня. Нульовий елемент масиву ar не використовується. Нижче наведено бінарне дерево і відповідне йому уявлення у вигляді масиву (зауважимо, що елементи в масиві йдуть в порядку обходу дерева зверху-вниз і зліва-направо):
Додавання елемента в чергу
Додавання - досить проста операція. Новий вузол дерева спочатку поміщається в самий його низ. Для цього новий вузол досить вставити за останнім вузлом в масиві (перший рядок функції). Нагадаємо, що, якщо ++ стоїть перед змінної, то спочатку вона збільшується на одиницю (нижче це збільшення числа вузлів ++ this.length дерева), а потім бере участь у вираженні: Опинившись останнім елементом масиву, вузол стає дочірнім для вузла з індексом length / 2 === i >> 1 ( "цілочисельне ділення"). Потім, його необхідно піднімати вгору по дереву до кореня (переставляючи з батьківськими вузлами місцями) до тих пір, поки він менше батька. Для операції менше за замовчуванням використовується функція: Функція перестановки i-того і j-того елементів масиву ar має вигляд:
Нижче наведені послідовні дії по додаванню нового вузла зі значенням 2 і його підйом вгору на належний для нього місце:
Виштовхування елемента з черги
Щоб виштовхнути мінімальний елемент з черги, необхідно виконати наступні дії. Спочатку міняємо місцями корінь і останній вузол дерева. Після цього, колишній корінь (мінімальний вузол) можна без проблем видалити, зменшивши число вузлів length--. Однак, колишній останній вузол, опинившись в корені, порушує властивості дерева. Тому його необхідно опустити вниз, змінюючи з своїми нащадками місцями, поки він не займе "належного" стану на дереві. Це станеться, коли обидва його нащадка виявляться більшими або рівними опускається вузлу. При опусканні, вузол змінюється з мінімальним з двох нащадків, щоб вище піднялося менше значення. Нижче наведено приклад, в якому вниз опускається ключ 5. після його обміну з коренем 1:
Відповідний код функції shift має вигляд: Вона використовує функцію "приведення в порядок" дерева, починаючи з вузла node і нижче:
Використання бінарної купи - це найпростіший спосіб організації пріоритетною черзі. Для підтримки властивостей купи при вставці і виштовхуванні вузла потрібно в середньому log2 N операцій, де N - число вузлів в дереві. За рахунок деякого ускладнення, можна отримати одиничну складність O (1) додавання (тобто швидкість додавання не залежить від числа вузлів). При цьому зберігається логарифмічна складність видаленні вузла. Відповідна структура даних називається купою Фібоначчі.
Звернемо увагу, що пріоритетна чергу одночасно є способом сортування (деяка сукупність величин поміщається в чергу, звідки витягується вже в заданому порядку).