19 lines
1.8 KiB
Markdown
19 lines
1.8 KiB
Markdown
#структура_данных #todo
|
||
|
||
![[Pasted image 20250124094602.png]]
|
||
|
||
> Минимальная куча — структура данных, построенная на базе деревьев. В таких кучах хранятся числа.
|
||
|
||
Минимальные кучи позволяют быстро найти наименьший элемент кучи, потому что наименьшее значение всегда находится в корне. Это самое важное свойство
|
||
минимальной кучи, и наименьший элемент находится за время $O(1)$.
|
||
|
||
Благодаря кучам проводить сортировку очень легко — просто продолжайте
|
||
запрашивать минимальное значение.И сохраняйте значения по порядку. В конце дерево будет пустым, а у вас появится отсортированный список чисел! Такой алгоритм называется пирамидальной сортировкой, или сортировкой кучей.
|
||
|
||
Максимальные кучи (невозрастающие пирамиды) очень похожи на минимальные, но у них в корне хранится наибольшее значение.
|
||
|
||
Кучи отлично подходят для реализации приоритетных очередей. Приоритетные очереди также используются для реализации эффективной версии [[Алгоритм Дейкстры (Dijkstra's algorithm)]].
|
||
|
||
|
||
Источники:
|
||
- [[Адитья Бхаргава - Грокаем Алгоритмы]] |