Является ли структура кучи уникальной при построении кучи?
Что такое куча?
Куча — это структура данных на основе дерева, где дерево — это полное двоичное дерево, которое поддерживает свойство, состоящее в том, что либо дочерние элементы узла меньше, чем он сам (максимальная куча), либо дочерние элементы больше, чем узел (минимальная куча).
Свойства кучи:
Структурное свойство: это свойство указывает, что это должно быть полное двоичное дерево.
Например:
Свойство упорядочения: куча должна следовать за свойством Max-heap или Min-heap.
- Если это Min-heap, родительский узел должен быть меньше дочернего узла и
- В случае Max-heap родительский узел должен быть больше дочернего узла.
Эти правила должны соблюдаться на каждом уровне, но порядок нижних дочерних узлов может измениться, мы можем понять это на примере (в качестве примера мы берем максимальную кучу):
Максимальная куча (рис. 1)
Макс. куча (рис. 2)
Является ли структура кучи уникальной?
Из приведенных выше двух примеров видно, что куча соответствует свойству Max-heap. И здесь мы также можем видеть, что в первом примере дочерними узлами нижнего уровня являются (5 и 4), (6 и 3), а во втором примере дочерними узлами нижнего уровня являются (4 и 5), ( 3 и 6). Меняется место узлов в нижней части кучи, но это удовлетворяет условию Max-heap.
- Порядок дочерних или листовых узлов не фиксирован, поэтому их будет 4! = 24 допустимых варианта размещения.
- То, какое расположение мы получим, зависит от порядка вставки и удаления или алгоритмов вставки и удаления. Или в случае создания кучи из массива (случай O (n)), порядок массива при запуске.
Вывод:
Из приведенных выше изображений мы можем заключить , что при построении кучи структура кучи не уникальна .