Алгоритмы, четвертая неделя
Часть 1: Приоритетные списки
Четвёртая неделя курса началась с изучения новых структур данных. Впервые речь о составных структурах данных зашла на второй неделе, когда изучались стеки и очереди. На четвёртой неделе изучалось нечто похожее идейно - приоритетные списки (не думаю, что перевёл грамотно, вообще говорят "Priority queues").
Как происходило удаление в предыдущих изученных типах данных? В стеках удалялся последний добавленный элемент, в очередях - первый, в рандомизированных очередях удалялся произвольный элемент. Потребность в приоритетных списках возникает, когда требуется удалять максимальные (или минимальные) элементы.
Скажем, может потребоваться искать M наибольших элементов в потоке из N объектов. Сортировка позволяет осуществлять это за линеарифмичное время, примитивный приоритетный список - за время порядка MN, двоичное дерево - за время NlogM. О двух последних способах речь пойдёт дальше.
Самый простой способ - держать элементы в неупорядоченном массиве. Тогда внесение нового элемента будет происходить мгновенно, но извлечение будет затруднительно - известно, что поиск максимального элемента в массиве пропорционально его размеру. Если это делать M раз, то как раз и получится MN. Упорядоченные массивы немного лучше - максимальный элемент находится мгновенно (всегда в конце или начале массива), но внесение нового элемента занимает довольно много времени - пропорционально размеру массива.
Хорошим способом является двоичное дерево, подчиняющееся простым принципам: индексирование начиначется с 1, а не с 0, объекты находятся в узлах, объект "родительского" узла не может быть меньше объектов, находящихся в узлах-потомках. В таком способе представления не требуется прописывать никаких дополнительных связей между узлами - потомками узла с индексом k являются узлы с индексами 2k и 2k + 1, предком узла с индексом k является, соответственно, узел с индексом k/2.
Как происходит построение такого двоичного дерева? Сценарий 1: объект-потомок становится больше объекта-предска. Чтобы избежать этого, надо всего лишь последовательно обменивать этот объект с объектами, значение которых меньше его, находящимися выше по дереву. Таким образом, больший объект как бы "всплывает" в направлении дерева до тех пор, пока не окажется меньше или равен объекту, находящемуся в узле-предке. Этот базовый сценарий используется при добавлении новых объектов в дерево: очередной объект добавляется в самый конец, после этого "всплывает" вверх. Сценарий 2: объект-предок становится меньше, чем один (или оба) его потомка. Для восстановления равновесия следует объект обменять с большим из его потомком и продолжать это, пока баланс не будет восстановлен. Иначе говоря, узел, нарушающий баланс дерева, "тонет" в направлении, обратном от корня дерева, до тех пор, пока равновесие не будет восстановлено.
Каково быстродействие такой структуры? Чтобы удалить максимальный элемет, нужно обменять значение корня дерева с последним элементом, затем "утопить" новый корень, то есть обменивать его с потомками, если его значение окажется меньше. В худшем случае эта операция потребует 2lgN сравнений. Чтобы добавить новый элемент, следует добавить его в конец дерева, а затем поднимать его вверх, то есть обменивать его значение с предком, если оно больше. Эта операция тоже пропорциональна логарифму от количества элементов.
Описанное двоичное дерево может быть легко использовано для сортировки массивов (к слову, именно этот способ я использовал для оптимизации одной из программ, доставшихся мне в наследство). Идея алгоритма сортировки деревом ("Heapsort" на английском) состоит в двух пунктах:
- Создать дерево из всех элементов массива
- Последовательно удалять максимальный элемент, записывая его в конец массива.
Какова эффективность такой сортировки? Создание дерева требует порядка 2N сравнений и перемещений, сортировка заниает меньше 2NlgN сравнений и перемещений. Этот алгоритм примечателен тем, что в любом случае его сложность не превышает ~NlgN и он не использует дополнительного места в памяти компьютера.
Часть 2: Таблицы символов
Таблицы символов являются обобщением идеи массивов. Массив позволяет установить связь индекса (натурального числа) с целым объектом, таблицы символы устанавливают связи между двумя объектами. Эта идея должна служить двум базовым целям: добавление нового объекта с заданным ключом и поиск объекта по заданному ключу. Пара "ключ - значение" и является обобщение идеи массива: заданное значение (объект) ищется по ключу.
Кроме добавления и поиска возможны и другие функции этой структуры данных, а именно: удаление значения, проверка, содержит ли таблица значение для заданного ключа, проверка таблица на пустоту, размер таблицы и итератор для всех ключей в таблице.
Если значения таблицы символов могут быть объектами любого типа и любой природы, то ключи таблицы должны поддаваться сравнению, аналогично целочисленным индексам массива - для того, чтобы поиск по таблице был вообще возможен.
Первый вариант реализации - динамически связанный список (стек), содержащий в качестве полей ключи и сами объекты. Поиск заданного ключа осуществляется простым перебором до тех пор, пока будет найдено нужное значение; добавление нового ключа осуществляется тоже перебором: если ключ найден, то обновляется его значение, если ключа нет, то добавляется новый элемент в начало списка. Оценка эффективности показывает, что добавление нового элемента в этой реализации в любом случае будет занимать линейное время, поиск в худшем случае будет пропорционален количеству элементов, в среднем случае - половине количества (N/2). Упорядоченной итерации по всем элементам эта реализация не осуществляет.
Второй вариант - упорядоченный массив пар "ключ-значение". Поиск в такой структуре осуществляется двоичным перебором и время этой операции логарифмично в худшем случае, а вот с добавлением нового ключа возникают проблемы: для этого придётся сдвигать все большие ключи, что является довольно дорогой операцией.
Список функций, которые также полезно иметь в этой структуре данных:
- определение ключа минимального/максимального элемента;
- определение наибольшего ключа, который меньше или равен заданному ключу;
- определение наименьшего ключа, который больше или равен заданному ключу;
- определение количества ключей, которые меньше/больше заданного ключа;
- выборка ключей заданного ранга;
- количество ключей, находящихся в заданном интервале;
- итерация по ключам в заданном интервале.
Эффективность почти всех этих функций в случае первой реализации (связанный список) линейна, кроме упорядоченной итерации - её порядок составляет NlogN (сортировка). В случае второй реализации (упорядоченный массив) ситуация поинтереснее: добавление/удаление и упорядоченная итерация линейны, функции поиска, ранга и т.д. логарифмичны, поиск максимального и выбор ключа заданного ранга выполняются моментально.
Казалось бы, реализация с помощью упорядоченного массива довольно эффективна, но то, что одни из самых часто используемых функций (добавление/удаление) выполняются за линейное время, не может устраивать. Существуют более подходящие реализации, которые были рассмотрены в следующих лекциях.