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

Если предполагается хранение кучи в линейном массиве с индексами вида i*N+{1..N} для потомков, то это compress всё равно будет полным перетасовыванием и заберёт почти всё сэкономленное раньше время. Просто взять и перенести целиком кусок дерева в другое место (как ты кажется предполагаешь, судя по «дети 4-ки теряются») можно только если узлы хранятся отдельно друг от друга и связываются явным образом через поля в структурах. А такое хранение тоже портит скорость кучи.

Чтобы сделать compress без таскания по одному элементу (во время ли забирания вершины, или потом всех вместе, но по одному), придётся делать слияние трёх получившихся веток, а это по-моему ещё дольше чем три раза утащить вниз получившиеся дырки.

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

Если предполагается хранение кучи в линейном массиве с индексами вида i*N+{1..N} для потомков, то это compress всё равно будет полным перетасовыванием и заберёт почти всё сэкономленное раньше время. Просто взять и перенести целиком кусок дерева в другое место (как ты кажется предполагаешь, судя по «дети 4-ки теряются») можно только если узлы хранятся отдельно друг от друга и связываются явным образом через поля в структурах. А такое хранение тоже портит скорость кучи.

Чтобы сделать compress без таскания по одному элементу (во время ли забирания вершины, или потом всех вместе, но по одному), придётся делать слияние трёх получившихся веток, а это по-моему ещё дольше чем три раза утащить вниз получившиеся дырки.

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