47
правок
Изменения
м
→Пример
Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции <tex>insert, next, delete</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени на одну операцию.
==== Пример ====
===== Типы операций:===== * Добавление элемента, который больше всех предыдущих.:
[[Файл:Operation1.jpg]]
* Замещение элемента более подходящим, т.е. добавление немаксимального элемента.:
[[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]]
===== {{Acronym |Последовательность: | именно она будет рассматриваться далее}}=====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
| 9 || 3 || 10 || 4 || 8 || 1 || 2 || 12 || 6 || 5 || 7 || 11
|}
===== Состояние очереди при каждом добавлении:=====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
