История изменений

Понимаешь какой ньюанс, ты не сделаешь алгоритма который будет требовать меньше операций сравнения чем у тебя операций пересчёта иск. Потому что на каждый пересчёт иск тебе нужен один инсерт в кучу (в старую, в новую - не важно, там будет сравнение для сортировки элементов в любом случае + операции смены адресов). Минимальная стоимость инсерта и поиска минимума (инвертируем числа и вместо максимума ищем минимум) в куче - O(1) и O(1), это, например, фиббоначиева куча.

Внезапно, то, что предложил я это ровно столько же операций сравнения. Вот только в моем варианте ёмкостная сложность O(1). А с кучей - O(n) и может плавать.

Поэтому куча это далеко не идеально тут.

Понимаешь какой ньюанс, ты не сделаешь алгоритма который будет требовать меньше операций сравнения чем у тебя операций пересчёта иск. Потому что на каждый пересчёт иск тебе нужен один инсерт в кучу (в старую, в новую - не важно, там будет сравнение для сортировки элементов в любом случае + операции смены адресов). Минимальная стоимость инсерта и поиска в куче - O(1) и O(1), это, например, фиббоначиева куча.

Внезапно, то, что предложил я это ровно столько же операций сравнения. Вот только в моем варианте ёмкостная сложность O(1). А с кучей - O(n) и может плавать.

Поэтому куча это далеко не идеально тут.