Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков.
В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-куча, поскольку корень поддерева является максимумом из значений элементов поддерева.
В качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами.
Двоичную кучу удобно хранить в виде одномерного массива, причем
- левый потомок вершины с индексом i имеет индекс 2*i+1,
- правый потомок вершины с индексом i имеет индекс 2*i+2.
Корень дерева (кучи) – элемент с индексом 0.
Высота двоичной кучи равна высоте дерева, то есть
log2 (N+1)↑,
где N – количество элементов массива, ↑ – округление в большую сторону до ближайшего целого.
Для представленной кучи
log2 (10+1)↑ = 3,46↑ = 4
Способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма оценивается как
N·log2N.
Можно построить кучу за N шагов. Для этого сначала следует построить дерево из всех элементов массива, не заботясь о соблюдении основного свойства кучи, а потом вызвать метод упорядочения для всех вершин, у которых есть хотя бы один потомок (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
Потомки гарантированно есть у первых heapSize/2 вершин, где heapSize – размер кучи.
Реализация класса кучи
public:
};
Конструктор кучи
}
Добавление элемента кучи
Новый элемент добавляется на последнее место в массиве, то есть позицию с максимальным индексом.
Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае новый элемент «поднимается» на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи.
Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна log2 N.
}
Вывод элементов кучи
Вывод элементов в форме кучи
}
Вывод элементов кучи в форме массива
}
Упорядочение кучи
}
В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав метод упорядочения для корня, то есть упорядочив все дерево.
Удаление вершины кучи (максимального элемента)
}
Пример Создать бинарную кучу из 16 элементов. Определить максимальный элемент.
}
Результат выполнения
Назад
Назад: Структуры данных