Двоєчний купик: Масив, що вважає себе деревом

Дерево, що ховається в масиві

Бінарний куч – це повне бінарне дерево — кожен рівень заповнений, крім можливо останнього, яке заповнюється зліва направо — зберігається без будь-яких покажчиків. Оскільки форма завжди однакова та передбачувана, діти вузла можна обчислювати лише за його індексом, тому все дерево живе в одному плоскому масиві:

parent(i) = (i - 1) >> 1 left(i) = 2*i + 1 right(i) = 2*i + 2 Без покажчиків батька та дитини, без викликів аллокатора для кожного вузла. Масив є щільним і зручним для кешування, що є однією з причин, чому кучі перемагають дерево на основі покажчиків на практиці, незважаючи на те, що обидва пропонують операції O(log n) на папері.

parent(i) = (i - 1) >> 1
left(i)   = 2*i + 1
right(i)  = 2*i + 2

Властивість кучі слабша, ніж здається

Мінімальний куч гарантує лише те, що кожен батько менший або рівний своїм дітям. Це не означає, що структура відсортована — куч нічого не говорить про порядок між двома суміжними вузлами, або між вузлом і його дядьком. Він лише обіцяє, що вершина дерева містить мінімум всього, що знаходиться нижче її. Ця слабка обіцянка є ключем: дотримання її потребує O(log n) операцій на зміну замість того, щоб O(log n) плюс ребалансування повністю відсортованої структури було потрібно.

Підняття (Sift-up): вставка значення

Вставка додає нове значення у перший вільний слот — наступне місце після останнього листка — що підтримує цілісність дерева. Це нове дерево тоді піднімається (sifts up): поки воно менше за свого батька, обмінюється з ним і повторює процес. Оскільки висота дерева дорівнює ⌊log₂ n⌋, то відбувається не більше ніж така кількість обмінів.

function siftUp(a, i) {
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (a[p] <= a[i]) break;
    [a[p], a[i]] = [a[i], a[p]];
    i = p;
  }
}

Відсортування вниз: вилучення мінімального елемента

Щоб видалити мінімальний елемент, візьміть значення кореня для повернення, перемістіть останній елемент масиву у слот кореня, зменште розмір масиву на одиницю та проведіть відсортування вниз: повторюйте обмін з меншим із двох дітей, поки воно не стане меншим або рівним обом дітям. Це коштує щонайбільше O(log n) операцій обміну і є операцією, яка називається алгоритмом Дейкстри, A* та кожним планувальником дискретно-подій на цьому сайті тисячі разів на секунду.

function siftDown(a, i, n) {
  for (;;) {
    let s = i, l = 2*i+1, r = 2*i+2;
    if (l < n && a[l] < a[s]) s = l;
    if (r < n && a[r] < a[s]) s = r;
    if (s === i) break;
    [a[s], a[i]] = [a[i], a[s]];
    i = s;
  }
}

Побудова кучі в O(n) та сортування heapsort

Виклик sift-up n разів для побудови кучі з нуля коштує O(n log n). Floyd у 1964 році запропонував кращий підхід: починати з останнього нелистового вузла та схиляти вниз кожен вузол віднизу до кореня. Здавалося б, це також має коштувати O(n log n), але насправді так не є – більшість вузлів розташовані біля нижньої частини дерева, де їх висота, а отже, і максимальна кількість обмінів, дуже мала. Підсумовуючи (висоту) помножену на (кількість вузлів на цій висоті) для всього дерева, отримуємо геометричну прогресію, яка збігається, даючи O(n) загалом. Повторний обмін кореня з останнім елементом та схилення зменшуваної кучі перетворює це на heapsort: сортування в найгіршому випадку з гарантованим часом виконання O(n log n), без додаткової пам’яті – хоча воно не є стабільним, оскільки рівні ключі можуть перетинатися під час обмінів.

Денрійські купи та де насправді зустрічаються купи

Бінарна куча – це d = 2 випадок більш загальної д-арної купи: кожен вузол має d нащадків замість 2. Більше значення d зменшує висоту дерева (менше рівнів переміщення вниз) за рахунок порівняння більшої кількості дітей на кожному рівні, щоб знайти найменший – 4-арні купи є поширеним оптимальним рішенням для алгоритмів типу Дейкстри, де виклики зменшення ключа значно переважують виклики видалення мінімума. Крім сортування, купи використовуються для підтримки відкритого набору в алгоритмах Дейкстри та A*, черги готовності в симуляторах подій та мереж, об'єднання упорядкованих пробілів розміром k-way, а також класичний трюк з двома купами для підтримки середнього значення в режимі реального часу: максимальну купу для нижньої половини даних і мінімальну купу для верхньої половини, підтримуючи їх на відстані одного елемента одна від одної.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Binary Heap і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.