3622
правки
Изменения
м
Нет описания правки
{{Определение
|definition='''Условие левосторонней кучи'''. Пусть <tex>dist(u)</tex> {{---}} расстояние от вершины <tex>u</tex> до ближайшей свободной позиции в ее поддереве. У пустых позиций <tex>dist = 0</tex>. Тогда потребуем для любой вершины <tex>u : dist(u.L)\ge dict(u.R)</tex>.}}
Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за <tex>O(1)</tex> поменять местами левого и правого ребенка, что не повлияет на порядок кучи.
