Сортировка кучей - максимальная куча

Хотя это не алгоритм сортировки кучи (сортирует набор данных с использованием кучи), создание кучи требует некоторой работы по сравнению, чтобы убедиться, что она остается кучей (вам нужна максимальная куча, поэтому все дочерние элементы меньше, чем их родитель ). Способ построить максимальную кучу состоит в том, чтобы поместить самый новый элемент в следующее доступное место (крайнее левое место в дереве, не заполненное в самой глубокой строке, или начать новую строку с самого левого места). Как только элемент вставлен, он заменяется своим родителем, если он больше, чем его родитель, пока он либо не станет корнем дерева, либо не найдет родителя больше, чем он сам. Это делается до тех пор, пока все элементы не будут вставлены, а у него, по сути, элемент max является корнем.

Важно отметить, что для минимальной кучи минимальным элементом является корень, поэтому вместо того, чтобы все родители были больше, чем их дочерние элементы, все дочерние элементы становятся больше, чем их родитель. При построении минимальной кучи по-прежнему добавляйте новые вершины в то же место, но меняйте местами новый потомок с их родителем, если дочерний элемент меньше родителя, а не больше.

Были прикреплены два изображения с полученными максимальными и минимальными кучами. Обратите внимание, что 89a соответствует первым 89, а 89b соответствует секундам, для пояснения. Максимальная куча Мин. куча