А Купа є особливим повне бінарне дерево . Оскільки купа є повним бінарним деревом, купа з Н вузлів має колода N висота. Корисно видалити найвищий або найнижчий пріоритетний елемент. Зазвичай це представлено як масив . Є два типи Heaps вMin-Heap
В Min-Heap ключ, присутній у кореневому вузлі, повинен бути меншим або рівним серед ключів, присутніх у всіх його дочірніх вузлах. Така сама властивість має бути рекурсивно істинною для всіх піддерев у цьому бінарному дереві. У Min-Heap мінімальний ключовий елемент, присутній у корені. Нижче наведено бінарне дерево, яке відповідає всім властивостям Min Heap.
машинопис кожн
Макс Хіп
В Макс-Хіп ключ, присутній у кореневому вузлі, повинен бути більшим або рівним серед ключів, присутніх у всіх його дочірніх вузлах. Така ж властивість має бути рекурсивно правда для всіх піддерев у цьому бінарному дереві. У Max-Heap максимальний ключовий елемент, присутній у корені. Нижче наведено бінарне дерево, яке відповідає всім властивостям Max Heap.
розмір шрифту латекс
Різниця між мінімальною та максимальною купою
| Мінімальна купа | Макс Хіп | |
|---|---|---|
| 1. | У Min-Heap ключ, присутній у кореневому вузлі, має бути меншим або дорівнювати ключам, присутнім у всіх його дочірніх вузлах. | У Max-Heap ключ, присутній у кореневому вузлі, повинен бути більшим або дорівнювати ключам, присутнім у всіх його дочірніх вузлах. |
| 2. | У Min-Heap мінімальний ключовий елемент, присутній у корені. | У Max-Heap максимальний ключовий елемент, присутній у корені. |
| 3. | Min-Heap використовує зростаючий пріоритет. | Max-Heap використовує низхідний пріоритет. |
| 4. | При побудові Min-Heap найменший елемент має пріоритет. | При побудові Max-Heap найбільший елемент має пріоритет. |
| 5. | У Min-Heap найменший елемент є першим, який виривається з купи. | У Max-Heap найбільший елемент є першим, який виривається з купи. |
Застосування Heaps :
- Сортування купи : Heap Sort є одним із найкращих алгоритмів сортування, які використовують Бінарна купа до сортувати масив в O(N*log N) час.
- Пріоритетна черга : Пріоритетну чергу можна реалізувати за допомогою купи, оскільки вона підтримує вставити() , видалити() , extractMax() , зменшитиКлюч() операції в O(log N) час.
- Найкоротший шлях Дейкстри і Мінімальне остовне дерево Прима .
Аналіз продуктивності Min-Heap і Max-Heap :
- Отримати максимальний або мінімальний елемент: O(1)
- Вставити елемент у Max-Heap або Min-Heap: O(log N)
- Видалити максимальний або мінімальний елемент: O(log N)