Просеивание и изменение ключа

Пирамидальная сортировка обходится одним просеиванием - вниз. Как только куча становится структурой, в которую что-то добавляют и в которой что-то меняют, нужно и второе.

Просеивание вверх

Элемент стал больше, чем положено, и нарушает инвариант со своим родителем. Меняем его с родителем и повторяем, пока родитель не окажется не меньше или пока не дойдём до корня.

int sift_up(vector<int>& a, int i) {          // нумерация с единицы
    while (i > 1 && a[i] > a[i / 2]) {
        swap(a[i], a[i / 2]);
        i /= 2;
    }
    return i;                                 // где элемент оказался
}

Стоит $O(\log n)$: глубина дерева и есть логарифм.

Нумерация: с нуля или с единицы

Формулы разные, и путать их дорого:

	с нуля	с единицы
дети $i$	$2i+1$, $2i+2$	$2i$, $2i+1$
родитель $i$	$\lfloor (i-1)/2 \rfloor$	$\lfloor i/2 \rfloor$
корень	0	1
последний с детьми	$n/2 - 1$	$n/2$

С единицы формулы короче и в них труднее ошибиться; с нуля - не надо держать пустую ячейку и совпадает с обычным массивом. Выбор безразличен, пока ответом не становится индекс: тогда условие задачи диктует одну из двух нумераций, и переводить придётся аккуратно.

Изменение ключа

Элемент уже лежит в куче, и его значение изменилось. Куда просеивать - определяется направлением изменения:

что случилось	что делать
значение выросло (в max-куче)	просеять вверх
значение упало	просеять вниз
неизвестно, куда изменилось	просеять вверх, и если не сдвинулось - вниз

Последняя строка - универсальный рецепт, и он же нужен при удалении произвольного элемента.

Почему это надо писать самому

В std::priority_queue изменить ключ уже лежащего элемента нельзя: она не даёт ни доступа к элементам, ни их позиций. Как только задача требует «уменьшить приоритет вершины» - как в алгоритме Дейкстры с честным decrease-key, - приходится либо писать кучу с массивом позиций, либо переходить на ленивое удаление.

Про однозначность

Пока в куче различные значения, обе процедуры детерминированы. С дубликатами появляется свобода, и если ответ - индекс, её надо чем-то убрать. Обычная договорённость такая:

Просеивание не двигает элемент при равенстве. То есть условие обмена строгое: a[i] > a[i/2], а не >=. Обмен равных кучу не портит, но он бесполезен и делает ответ неоднозначным.

При двух равных детях выбирается левый. Тогда просеивание вниз тоже становится однозначным.

Это не свойство кучи, а соглашение. Но соглашение важное: без него две правильные реализации дают разные индексы, и задача перестаёт быть проверяемой.

Проверено: реализация с этими двумя правилами воспроизводит все примеры из задач про кучу, где ответом служит индекс, - в том числе те, где в куче лежат три одинаковых значения.