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