„Група“ е специализирана дървовидна структура от данни, която удовлетворява свойството на купчина: Ако „A“ е родителски възел на „B“, тогава ключът (стойността) на възел „A“ е подреден по отношение на ключ на възел „B“ със същия ред, който се прилага в купчината. Купчината може да бъде класифицирана допълнително като „максимална купчина“ или „минумна купчина“. В max-heap ключовете на родителските възли винаги са по-големи или равни на тези на децата и най-високият ключ е в основния възел. В min-heap ключовете на родителските възли са по-малки или равни на тези на децата и най-ниският ключ е в основния възел.
Купчината е едно максимално ефективно изпълнение на абстрактен тип данни, наречен „приоритетна опашка“, и всъщност приоритетните опашки често се наричат „купчини“, независимо от това как могат да бъдат реализирани. Често срещана реализация на купчина е двоичната купчина, в която дървото е пълно двоично дърво.
Структурата на данните на купчината, по-специално двоичната купчина, беше въведена като структура на данните за алгоритъма за сортиране на „heapsort“. Купчините също са от решаващо значение в няколко ефективни алгоритъма на графики, като например „алгоритъмът на Дейкстра“. В куп елементът с най-висок (или най-нисък) приоритет винаги се съхранява в основата. Купчината не е сортирана структура и може да се разглежда като частично подредена. Няма конкретна връзка между възлите на дадено ниво, дори между братята и сестрите. Когато купчината е пълно двоично дърво, тя има най-малката възможна височина — купчина с `N` възли винаги има `log N` височина. Купчината е полезна структура от данни, когато трябва да премахнете обекта с най-висок (или най-нисък) приоритет.
В тази публикация сме изброили често задавани въпроси за интервю, които използват структура на купчини данни:
- Въведение в приоритетните опашки, използващи двоични купчини
- Реализация на минимална купчина и максимална купчина — C++, Java
- Проверете дали даден масив представлява min-heap или не
- Преобразуване на максимална купчина в минимална купчина в линейно време
- „Намерете k’-ия най-голям елемент в масив“
- Сортиране на k-сортиран масив
- Обединяване на `M` сортирани списъци с променлива дължина
- „Намерете k’тия най-малък елемент в масива“
- Намерете най-малкия диапазон с поне един елемент от всеки от дадените списъци
- Обединяване на `M` сортирани списъци, всеки от които съдържа `N` елемента
- Намиране на първите `k` неповтарящи се символа в низ с едно обхождане
- Свържете `n` въжета с минимални разходи
- „Връщане на k’тия най-голям елемент в поток“
- „Алгоритъм за компресиране на кодиране на Хъфман“
- Замяна на всеки елемент от масива със съответния му ранг
- „Най-кратките пътища от един източник – Алгоритъмът на Дейкстра“
- „Построяване на декартово дърво от обхождане в непорядък“
- „Структура на данните за Treap“
- Внедряване на структура на данни на Treap (вмъкване, търсене и изтриване)
- „Алгоритъм за сортиране на купчина“
- Алгоритъм за Introsort — Общ преглед и внедряване на C++
- Външен алгоритъм за сортиране чрез сливане
- Ефективно обединяване на `k` сортирани свързани списъци
- Проверете дали едно двоично дърво е min-heap или не
- Преобразуване на двоично дърво за търсене в Min Heap
- Намерете първите `k` максимум срещащи се думи в даден набор от низове
Благодаря ви.
