1 голос
 
1357 просмотров
3.09.2016 / 11:32  riseremi

Что такое куча (heap) и чем она полезна?

Читал про структуры данных, дошёл до кучи (heap) и ничего не понимаю. Какие-то узлы, двоичные деревья, максимум и минимум. Помогите пожалуйсута!!!
Ответы
 
6 голосов
 
# 3.09.2016 / 13:29  Oak
Heap (по русски называется пирамида) -- интересная стурктура данных, представляемая обычно в виде бинарного дерева и используемая для построения приоритетных очередей, пирамидальной сортировки (также известной, как heapsort) и других алгоритмов, которые работают с графами. Характеиризуется в основном временем вставки и удаления за O(log n).

Основными свойствами (и условиями корректности) пирамиды являются:
1. Полнота -- пирамида представляется в виде дерева, в котором все уровни польностью заполнены кроме, возможно, последнего.
2. Эффективная реализация в виде массива -- так как пирамида (обычно бинарное дерево) обладает полнотой, то реализация такой структуры в виде массива крайне эффективна.
3. Каждый узел в пирамиде либо равен, либо больше сввоих потомков.

Таким образом, пирамида -- эфективная структура данных для тех случаев, когда нужна эффективная вставка элементов в относительно отсортированную структуру данных, а затем получение максимального (или минимального) элемента -- это, кстати, можно считать описанием пирамидальной сортировки.

Удаление из кучи наибольшего (наименьшего) элемента осуществляется в три шага:
1. Удаление корня дерева (получение элемента)
2. Перемещение крайнего нижнего элемента в корень (он является противоположным корню -- наименьшим, если корень наибольший и т.д.), такой элемент в представлении в виде массива обычно оказывается последним. Такой шаг обеспечивает полноту пирамиды.
3. Пошаговое смещение нового корневого элемента вниз по дереву. Тут мы на каждом шаге заменяем наш элемент с наибольшим его потомком, пока он не окажется больше обоих потомков.

Извиняюсь, что без иллюстраций.
Всего: 1

Реклама

Мы в соцсетях

tw tg yt gt