Тип структуры данных, очень распространенный и очень используемый - Heap. Эта структура данных характеризуется отношением, наложенным на его узлы: если < является отношением, а node является узлом, то node < node.child для всех дочерних элементов node.
Но что происходит, когда вам нужно изменить отношения?
Способ грубой силы состоит в том, чтобы просто извлечь все элементы из Heap и добавить их к другому Heap, имеющему желаемое отношение: обычно это занимает O(n log(n)) время. Существует ли Heap, который позволяет быстрее изменять его отношения, возможно, с помощью алгоритма на месте?