⛰️ Бінарна купа
Черга з пріоритетом як масив
Налаштування
Статистика
Розмір купи
0
Порівняння
0
Обміни
0
Остання операція
Готово
Довідка та теорія

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

Представлення масивом

Оскільки дерево завжди повне, покажчики не потрібні. Для вузла з індексом i його предок знаходиться за індексом ⌊(i−1)/2⌋, а нащадки — за 2i+1 та 2i+2. Форма дерева повністю визначається схемою індексації.

Спливання (вставка)

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

Занурення (видалення мінімуму)

Видалення мінімуму обмінює корінь з останнім елементом, зменшує масив на один, а потім повторно обмінює новий корінь з меншим із нащадків, доки властивість купи не відновиться. Також O(log n).

Побудова купи Флойда за O(n)

Виклик занурення для кожного внутрішнього вузла, починаючи з ⌊n/2⌋−1 і закінчуючи 0, будує купу з n довільних значень. Хоча це виглядає як O(n log n), більшість вузлів розташовані ближче до низу дерева, де занурення проходить лише короткий шлях; сумарна робота по всіх рівнях утворює збіжний ряд, що дає O(n).

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

Бінарні купи ефективно реалізують черги з пріоритетом, лежать в основі пірамідального сортування (сортування на місці за O(n log n)) та підтримують фронт алгоритмів Дейкстри й Прима, де потрібно постійно знаходити й видаляти наступний найдешевший елемент.

Про бінарну купу — чергу з пріоритетом

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 11 липня 2026 р.

Бінарна купа — це повне бінарне дерево, у якого кожен рівень заповнений повністю, крім, можливо, останнього, що заповнюється зліва направо, і яке компактно зберігається у звичайному масиві без жодних покажчиків. Для будь-якого індексу i предок знаходиться за індексом ⌊(i−1)/2⌋, а нащадки — за 2i+1 і 2i+2, тож структура дерева повністю визначена самою схемою індексації. Мін-купа підтримує властивість купи: значення кожного предка менше або дорівнює обом його нащадкам, тому найменший елемент завжди перебуває за індексом 0, хоча сам масив загалом не відсортований. Вставка значення додає його в кінець і піднімає вгору (спливання), обмінюючи з предком, поки властивість купи порушена — операція за O(log n), обмежена висотою дерева. Видалення мінімуму обмінює корінь з останнім елементом, зменшує масив і опускає новий корінь донизу (занурення) до меншого з нащадків, знову за O(log n). Побудова купи з n невідсортованих значень зануренням від останнього внутрішнього вузла виконується загалом за O(n), а не O(n log n), оскільки більшість вузлів розташовані ближче до низу, де занурення виконує мало роботи. Бінарні купи лежать в основі черг з пріоритетом, пірамідального сортування та алгоритмів Дейкстри й Прима.

Часті запитання

Чому бінарну купу можна зберігати в масиві без покажчиків?

Оскільки це повне бінарне дерево, заповнене рівень за рівнем без пропусків, предок і нащадки вузла обчислюються напряму з його індексу в масиві (предок = ⌊(i−1)/2⌋, нащадки = 2i+1 та 2i+2). Це уникає накладних витрат пам'яті на вузли дерева з покажчиками і дає чудову локальність кешу порівняно зі зв'язаними структурами.

У чому різниця складності між спливанням і зануренням?

Обидві операції виконуються за O(log n) у найгіршому випадку, оскільки кожна проходить лише один шлях від кореня до листка довжиною ⌊log₂ n⌋. Спливання робить не більше одного порівняння на рівень (з предком), тоді як занурення робить до двох порівнянь на рівень (з обома нащадками), тому занурення має трохи більший сталий множник, попри однакову асимптотичну оцінку.

Чому побудова купи з n елементів виконується за O(n), а не O(n log n)?

Алгоритм побудови купи Флойда викликає занурення лише для внутрішніх вузлів, починаючи з останнього і рухаючись до кореня. Більшість вузлів розташовані ближче до низу дерева, де занурення проходить лише короткий шлях; сумарна робота по всіх рівнях утворює геометричний ряд, що збігається до O(n), на відміну від O(n log n) при послідовній вставці n елементів по одному.

Яка різниця між мін-купою та макс-купою, і як купа порівнюється зі збалансованим ДДП для черги з пріоритетом?

Мін-купа тримає найменше значення в корені (предок ≤ нащадки); макс-купа тримає найбільше (предок ≥ нащадки) — застосовуються ті самі алгоритми з оберненим порівнянням. Порівняно зі збалансованим двійковим деревом пошуку, купа дає ту саму складність O(log n) для вставки й видалення мінімуму, але з простішою реалізацією на масиві, без логіки перебалансування та з O(1) для перегляду мінімуму, тоді як ДДП пропонує впорядкований обхід і пошук за довільним ключем за O(log n), чого купа не підтримує.