\Section{Cтруктуры данных}{21 сентября}{Глеб Винерский}

\Subsection {Избавление от амортизации. Ленивое копирование}

\begin{MyList}

\item {\bf Вектор \NO{1} }

Время работы практически всех операций вектора чистое $O(1)$. Исключение - операция push\_back, которая работает за амортизированную константу, так как если приходится удваивать размер вектора, то push\_back отработает за линию.

Удвоение вектора состоит из трех этапов:

1)Выделение памяти для нового вектора

2)Копирование элементов из старого вектора в новый

3)Освобождение памяти из-под старого вектора

Выделение и освобождение памяти технически зависимые действия, и с точки зрения алгоритмизации мы не можем на них повлиять. Заметим лишь, что если теоретически они работают за $\Theta(n)$, то на практике они намного быстрее и здесь мы можем считать их время работы равным $O(1)$.

Копирование же в стандартной реализации вектора работает за $\Theta(n)$ и его оптимизацией мы и займёмся. Давайте вместо единоразового копирования всех элементов разобьём его на много маленьких операций, которые мы будем выполнять параллельно с работой основных операций вектора. Выделим для нового вектора память в 2 раза больше размера старого, где первая половина будет соответствовать уже существующим элементам, а во второй будет элемент, добавление которого и потребовало выделение памяти. Но мы не будем копировать все элементы в новый вектор, а будем некоторое время хранить оба и при обращении к элементу, проверять в каком векторе он находится. Копировать же мы будем по одному элементу при каждом вызове push\_back и pop\_back. Тогда, так как мы копируем по одному элементу при вызове push\_back, то как только память нового вектора заполнится, все старые элементы гарантированно будут скопированы, и значит мы сможем его удалить, и нам никогда не придётся хранить больше двух векторов. В pop\_back же копирование необходимо, чтобы избежать затирания элементов в новом массиве при поочерёдном вызове push\_back, pop\_back. Таким образом, если обозначить старый вектор $a$, новый $b$, а номер последнего нескопированного элемента $k$, то код функций теперь выглядит так:

\begin{code}
at*(i)
    if i <= k
        return a.at(i)
    else
        return b.at(i)

copy()
    if k >= 0
        b[k] = a[k]
        k-- 

push_back*()
    push_back()
    copy()

pop_back*()
    pop_back()
    copy()

\end{code}

\item {\bf Вектор \NO{2}}

В первом варианте мы избавились от линейного копирования, разбив его на поэлементный перенос элементов параллельно с работой функций вектора. Но можно копировать элементы не после того, как он заполнился, а заранее. Как только у вектора заполнилась половина ячеек, заведём новый удвоенный вектор и будем переносить в него элементы аналогично прошлой реализации. Единственное отличие,  что здесь копировать нужно не по одному, а по два элемента, тогда к моменту заполнения старого вектора все его элементы уже будут перенесены в новый, и старый можно будет удалить.

\item {\bf HashTable}

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

\item {\bf Очередь с минимумом}

Здесь мы рассматриваем очередь с минимумом на двух стеках. В обычной реализации очередь с минимумом работает за амортизированную константу, так как если при извлечении элемента, выходной стек окажется пуст, то операция отработает за $O(n)$. Для избавления от амортизации давайте воспользуемся уже знакомым по предыдущим пунктам методом ленивого копирования. Как только размер выходного стека становится меньше входного, начинаем копировать элементы входного стека в выходной. Давайте хранить стеки на массиве, причём обе границы стека могут в нём смещаться. Тогда, когда начинается копирование, мы отрезаем от входного стека все его элементы и приравниваем левую и правую границы $R+1$. И копируем эти элементы "под дно" выходного стека. Тогда для восстановления нормального состояния очереди нам понадобится: a) скопировать n элементов из одного стека в другой, b)посчитать частичные минимумы на $n$ копируемых элементах и на $\le n$ элементах оставшихся в выходном стеке. Итого $3n$ операций и значит при обработке каждого $push$ и $pop$ необходимо выполнить 3 операции. Осталось научиться обрабатывать запросы минимума в процессе перестройки очереди. Для этого надо лишь отдельно запомнить минимум на копируемом участке, который заранее доступен на его вершине, и при обработке запроса брать минимум из обоих стеков и копируемого участка.

\end{MyList}


\Subsection {Куча(Heap)}

Куча - бинарное дерево, которое, если обозначить вершины $h_i$, а вершина имеет номер 1, удовлетворяет свойствам:

$h_i \le h_{2i}$

$h_i \le h_{2i{+}1}$

Куча по определению выполняет две операции:

ExtractMin() - извлечь из кучи элемент с минимальным ключом

Add(x) - добавить в кучу элемент с ключом x

В stl структурой с такими операциями является priority\_queue.

Однако, список возможностей кучи можно расширить ещё 2мя операциями:

Delete() - удалить элемент из кучи

DecreaseKey(y) уменьшить ключ элемента до y

Которые в свою очередь выражаются одна через другую:

Delete() = DecreaseKey(${-}\infty$) + ExtractMin()

DecreaseKey(y) = Delete() + Add(y)

Получившуюся структуру называют ExtendedHeap.

{\bf Реализация}

Мы будем реализовывать кучу на массиве. У корня будет индекс 1, а индексы сыновей вершины $i$: $2i$ и $2i+1$, тогда индекс родителя $j$ой вершины $\lfloor j/2 \rfloor$.

Заведём две вспомогательные функции: SiftUp(i) и SiftDown(i), которые будут просеивать $i$ую вершину соответственно верх или вниз, пока она не займёт корректную позицию.

\begin{code}

SiftUp(i)
    while i>1 && h[i/2] > h[i]
        swap(h[i], h[i/2])
        i /= 2

SiftDown(i)
    while i <= n
        m = min(i, 2i, 2i+1) // min(h[i], h[2i], h[2i+1])
        if(m == i)  break
        swap(h[m], h[i])
        i = m

\end{code}

Теперь с их помощью можно реализовать основные операции кучи.

\begin{code}

Add(x)
    h[++n] = x
    SiftUp(n)

ExtractMin()
    result = h[1]
    swap(h[1], h[n--])
    SiftDown(1)
    return result

\end{code}

Теперь оценим время работы Add и ExtractMin. В худшем случае SiftUp и SiftDown пройдут всё дерево снизу вверх/сверху вниз. Высота бинарного дерева из $n$ вершин $\lceil \log_2(n+1) \rceil$. Значит время работы Add и ExtractMin  $O(\log n)$.

{\bf HeapSort}

Одним из наиболее распространённых применений кучи является HeapSort(пирамидальная сортировка). Алгоритм представляет собой добавление всех элементов в кучу и извлечение их из неё. Тогда первый извлечённый элемент будет минимумом на всём массиве, второй извлечённый минимумом среди всех кроме первого, и так далее. Тогда, так как мы добавляем в кучу $n$ элементов, а затем $n$ элементов извлекаем, то суммарное время работы HeapSort $O(n \log n)$:

\begin{code}

Heapsort()
    For(i, n)
        heap.Add(a[i])
    For(i, n)
        a[i] = h.ExtractMin()

\end{code}

Важной оптимизацией в HeapSort, и других алгоритмах, строящих кучу по известному количеству элементов, является построение за $O(n)$. Для этого будем строить кучу не в отдельном массиве, а прямо в массиве $a$ (Inplace):

\begin{code}

Build()
    For i = n..1
       Sift Down(i)

\end{code}

Время работы = $\sum\limits_{k=1}^{\log n} k \lfloor \frac{n + 1}{2^k} \rfloor \le (\sum\limits_{k=1}^\infty \lfloor \frac{k}{2^k} \rfloor)(n+1) = \Theta(1)\Theta(n) = \Theta(n)$

