У меня есть вопрос, что в структуре данных кучи левый ребенок может быть больше, чем правильный ребенок на своем собственном уровне? Я имею в виду, что рассмотрю эти три числа 9,5,8, и я хочу создать структуру данных с максимальной суммой, так что корень будет равен 9, и верно ли, что 8 - его левый ребенок, а 5 - его правильный ребенок? , пожалуйста, помогите мне спасибоо куче (max-heap и min heap)
Это не имеет значения. У узла в макс-куче должны быть дети, которые ниже, а узел в мини-куче должен иметь детей, которые больше. Это единственные требования.
Max-Heap свойства:
Мин-вороха свойства:
Следовательно, куча не подходит для поиска, но используется для сортировки массива элементов, поскольку поиск принимает линейное время O (n).
Для поиска мы всегда можем искать деревья двоичного поиска (BST), которые делают то же самое в O (h) времени. И в лучшем случае он выполнит поиск в O (logn), если дерево BS будет сбалансировано.
так что нет правила для того, как мы устанавливаем левый и правый дочерний элемент родителя? Потому что куча почти полного двоичного дерева, и я думаю, что это было правилом в двоичном дереве, которое оставило ребенка, должно быть меньше этого правильного ребенка! Я думаю, что для моего приведенного выше примера я должен написать «root: 9» и «leftChild: 5» и «rightChild: 8», не так ли? – user355002
Как обычно вы создаете максимальную кучу, нужно начинать посередине массива до первого элемента и рекурсивно позволять каждому узлу просачиваться вниз через дерево, обменивая узлы. Это можно сделать в O (n) времени. Это не двоичное дерево поиска, поэтому нет особых связей между узлами-братьями, кроме того, что они меньше (или больше в случае мини-кучи), чем их родитель. –
aha, и если мы хотим найти ключ в этой структуре данных, нам не нужно делать это как двоичное дерево поиска? – user355002