Зміст:
Визначення - Що означає Heap?
Купа, в контексті структури даних, - це структура даних на основі дерева, яка задовольняє властивості купи, де кожному елементу присвоюється ключове значення або вагова вага. Ключ із нижчим значенням завжди має батьківський вузол з ключем більш високого значення. Це називається max-heap структура, і серед усіх вузлів кореневий вузол має найвищий ключ.
Іноді структура на основі дерева має правило зворотної структури, де елемент з ключем більш високого значення завжди має ключ нижчого значення як батьківський вузол. Це називається структурою min-heap, і серед усіх вузлів кореневий вузол має найнижчу клавішу.
Техопедія пояснює Хіпу
Не існує жодних практичних обмежень щодо кількості дітей, які кожен вузол може мати в купі, навіть якщо у кожного вузла зазвичай два, максимум. Купа вважається найефективнішою реалізацією абстрактного типу даних, що називається чергою пріоритетів. Реалізація купи має важливе значення в різних алгоритмах графіків (включаючи алгоритм Діккстри), а також в алгоритмі сортування грудей.
Heaps має кілька варіацій, які виконують роль абстрактних черг пріоритетних типів даних з високою ефективністю. У багатьох програмах, таких як алгоритми графіків, потрібна реалізація черг пріоритетів.
Масив - найпоширеніша форма реалізації купи, де не потрібні вказівники для зв’язку між її елементами.
Heap виконує кілька операцій, включаючи:
- Find-max: шукає найвищий ключовий вузол серед групи вузлів
- Find-min: Пошук найнижчого ключового вузла серед групи вузлів
- Delete-max: Видаляє найвищий ключовий вузол серед групи вузлів
- Delete-min: Видаляє найнижчий ключовий вузол серед групи вузлів
Купи також включають функції, які виконують злиття, вставлення та зміни ключів.
Це визначення було написане в контексті структури даних
