Реферат: Структуры данных


Структуры данных


При решении любой задачи возникает необходимость работы с данными и выполнения операций над ними. Набор этих операций для каждой задачи, вообще говоря, свой. Однако, если некоторый набор операций часто используется при решении различных задач, то полезно придумать способ организации данных, позволяющий выполнять именно эти операции как можно эффективнее. После того, как такой способ придуман, при решении конкретной задачи можно считать, что у нас в наличии имеется «черный ящик» (его мы и будем называть структурой данных), про который известно, что в нем хранятся данные некоторого рода, и который умеет выполнять некоторые операции над этими данными. Это позволяет отвлечься от деталей и сосредоточиться на характерных особенностях задачи. Внутри этот «черный ящик» может быть реализован различным образом, при этом следует стремиться к как можно более эффективной (быстрой и экономично расходующей память) реализации. Этот материал посвящен описанию некоторых часто используемых на практике структур данных и способов эффективной реализации этих структур. Описываемые структуры часто сопровождаются примерами задач, в которых они могут быть применены.


п1) Простые структуры данных.


В этом пункте мы рассматриваем некоторые простые структуры данных. Материал разделен на три части: очереди и стеки, списки, структуры для представления графов. Сведения эти излагаются достаточно кратко и не сопровождаются примерами, так как множество различных областей теории алгоритмов (в частности, теория графов, которая, хотелось бы надеяться, будет излагаться на этих сборах) содержат значительное количество примеров применения этих структур, так что примеры, наверное, будут рассмотрены на последующих теоретических занятиях.


a) ^ Очереди и стеки.


Иногда возникает необходимость обработки данных в некотором порядке. Часто встречаются следующие ситуации:

1) Данные нужно обрабатывать в порядке их получения.

2) Данные нужно обрабатывать в порядке, обратном порядку получения.


Структуру данных «очередь» (queue), удобно применять в первой ситуации. Эта структура поддерживает следующие операции:

QUEUE-INIT – инициализирует (создает пустую) очередь;

ENQUEUE (x) – добавляет в очередь объект x;

DEQUEUE – удаляет из очереди объект, который был добавлен раньше всех, и возвращает в качестве результата удаленный объект (предполагается, что очередь не пуста);

QUEUE-EMPTY – возвращает TRUE, если очередь пуста (не содержит данных), и FALSE – в противном случае.

Опишем реализацию очереди на базе массива. Будем использовать для хранения данных массив Q[1..N], где число N достаточно велико. При этом данные всегда будут храниться в некотором интервале из последовательных ячеек этого массива. Мы будем использовать переменные Head и Tail для указания границ этого интервала. Более точно, данные хранятся в ячейках с индексами от Tail+1 до Head (предполагается, что Tail < Head; если же Head = Tail, то очередь пуста). Соблюдается также следующее правило: чем позже был добавлен в очередь объект, тем большим будет индекс ячейки массива, в которую он помещается. Это означает, что объект, который был добавлен в очередь раньше всех – это Q[Tail+1].

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


Operation QUEUE-INIT

Head:= 0;

Tail:= 0;

End;


Operation ENQUEUE (x)

Head:= Head+1;

Q[Head]:= x;

End;


Operation DEQUEUE

Tail:= Tail+1;

Return Q[Tail];

End;


Operation QUEUE-EMPTY

If Tail < Head

Then Return FALSE

Else Return TRUE;

End;


Все операции над очередью при такой реализации работают за O(1), следовательно, такая реализация эффективна по времени. Однако, число N нужно выбирать достаточно большим (в зависимости от задачи), чтобы избежать «переполнения» очереди, то есть ситуации, когда Head > N. Это может приводить в некоторых задачах к неэффективному использованию памяти. Альтернативная реализация очереди может быть построена на базе списков (см. следующий раздел).


Структуру данных «стек» (stack) удобно применять во второй ситуации. Она во многом аналогична очереди, за исключением того, что из стека удаляется тот объект, который был добавлен позже всех (а не раньше всех, как в очереди). Итак, стек поддерживает следующие операции:

STACK-INIT – инициализирует стек;

PUSH (x) – добавляет в стек объект x;

POP – удаляет из стека объект, который был добавлен позже всех, и возвращает в качестве результата удаленный объект (предполагается, что стек не пуст);

STACK-EMPTY – возвращает TRUE, если стек пуст, и FALSE – в противном случае.

Стек будем реализовывать также на базе массива S[1..N]. Данные будем хранить в некотором интервале последовательных ячеек массива (более точно, в ячейках с индексами от 1 до Top). Top – переменная, которая содержит текущее количество объектов в стеке. Как и в случае очереди, соблюдается правило: если i < j Top, то объект S[i] был добавлен в стек раньше, чем объект S[j]. Это гарантирует, что объект S[Top] – тот объект, который был добавлен в стек позже всех.

Псевдокод операций над стеком может быть следующим:


Operation STACK-INIT

Top:= 0;

End;


Operation PUSH (x)

Top:= Top+1;

S[Top]:= x;

End;


Operation POP

Top:= Top-1;

Return S[Top+1];

End;


Operation STACK-EMPTY

If Top > 0

Then Return FALSE

Else Return TRUE;

End;


Реализованные операции, работают, очевидно, эффективно по времени – за O(1). Однако, использование памяти, как и в случае очереди, может оказаться в некоторых задачах неэффективным.


б) ^ Списковые структуры


Список – это структура, в которой данные выписаны в некотором порядке. Однако, в отличие от массива, этот порядок определяется указателями, связывающими элементы списка в линейную цепочку. Обычно элемент списка представляет собой запись, содержащую ключ (идентификатор) хранящегося объекта, один или несколько указателей и необходимую информацию об объекте. Под ключом подразумевается какая-либо величина, идентифицирующая объект. К примеру, если мы храним информацию о городах, то ключом может быть название города.

Над данными поддерживаются следующие операции:

LIST-INIT – инициализирует список;

LIST-FIND (k) – возвращает TRUE, если в списке есть объект с ключом k, иначе возвращает FALSE;

LIST-INSERT (obj) – добавляет в список объект obj;

LIST-DELETE (x) – удаляет из списка элемент x.

Возможна различная связь данных в списке. Если каждый элемент списка содержит указатель на элемент, следующий непосредственно за ним, то получаемый список называют односвязным. Если в дополнение к этому каждый элемент списка содержит указатель на элемент, следующий непосредственно перед ним, то список называют двусвязным. Обычно у последнего элемента списка указатель на следующий элемент равен NIL. Но в некоторых списках удобно, чтобы этот указатель показывал на первый элемент списка. Таким образом, список из цепочки превращается в кольцо. Такие списки (односвязные и двусвязные) называют кольцевыми.

Опишем реализацию всех операций для двусвязного некольцевого списка. Каждый элемент списка будем хранить как запись, содержащую следующие поля: Key – ключ объекта, Data – дополнительная информация об объекте, Next – указатель на следующий элемент списка (Next = NIL у последнего элемента списка), Prev – указатель на предыдущий элемент списка (Prev = NIL у первого элемета списка). Будем всегда поддерживать указатель Head на первый элемент списка (если список пуст, то Head = NIL). Будем считать, что добавляемые объекты – записи, содержащие поля Key – ключ и Data – дополнительная информация.

Реализация операции LIST-INIT тривиальна:


Operation LIST-INIT

Head:= NIL;

End;


Операция LIST-INIT, очевидно, выполняется за O(1).

Для реализации операции LIST-FIND нужно просмотреть все элементы списка в поисках нужного.


Operation LIST-FIND (k)

X:= Head;

While X <> NIL Do Begin

If X^.Key = k

Then Return TRUE;

X:= X^.Next;

End;

Return FALSE;

End;


Операция LIST-FIND выполняется за O(n), где n – количество элементов в списке. Это означает, что список не является структурой, эффективно выполняющей поиск.

При добавлении элемента в список можно вставить его в начало списка, при этом нужно переписать некоторые указатели.


Operation LIST-INSERT (obj)

New(X);

X^.Key:= obj.Key;

X^.Data:= obj.Data;

X^.Next:= Head;

X^.Prev:= NIL;

If Head <> NIL

Then Head^.Prev:= X;

Head:= X;

End;


Операция LIST-INSERT выполняется за O(1).

Наконец, при удалении элемента из списка нужно соединить указателями предыдущий и следующий за ним элементы. При этом нужно аккуратно обработать случай, когда элемент является первым или последним в списке.


Operation LIST-DELETE (x)

If x^.Prev <> NIL

Then x^.Prev^.Next:= x^.Next

Else Head:= x^.Next;

If x^.Next <> NIL

Then x^.Next^.Prev:= x^.Prev;

Dispose(x);

End;


Операция LIST-DELETE выполняется за O(1), однако для ее выполнения нужно иметь указатель на удаляемый элемент списка. Если этот указатель неизвестен, то удаляемый элемент нужно сначала найти, для чего придется просмотреть (в худшем случае) весь список, и удаление будет работать за O(n), где n – количество элементов в списке.


Упражнение 1. Опишите реализацию всех операций для других видов списков. Укажите достоинства и недостатки каждого из видов.

Упражнение 2. Реализуйте очередь и стек на базе списочной структуры. Укажите достоинства и недостатки такой реализации.


в) ^ Способы хранения графов.


Вообще говоря, данный вопрос не принято относить к теме «структуры данных». Однако, в принципе, граф можно рассматривать как структуру данных, а любой способ его хранения – как реализацию этой структуры данных (мы так делать не будем). К тому же, в данном разделе мы увидим пример эффективного применения списков, описанных в предыдущем разделе.

Для начала проясним, что такое граф. Рассмотрим произвольный конечный непустой набор (множество) объектов V. Назовем эти объекты вершинами, а набор V – множеством вершин. Рассмотрим теперь некоторый конечный набор (множество) E, состоящий из пар вида (a, b), где и (). Будем полагать, что все пары в E попарно различны. Эти пары называются ребрами, а набор E – множеством ребер. Двойка G = (V, E) называется (конечным) ориентированным графом. Можно наглядно представить понятие граф, если для каждой вершины нарисовать точку, и для каждого ребра (a, b) провести стрелку от точки, обозначающей вершину a, к точке, обозначающей вершину b. Нарисованная схема напоминает карту однонаправленных дорог, соединяющих некоторые города. И в самом деле, графы часто применяют для моделирования различных транспортных сетей. Однако, область применения графов этим не ограничивается. Если вместе с каждым ребром (a, b) граф содержит и ребро (b, a), то такой граф называют неориентированным. На рисунке ребра такого графа изображают не стрелками, а линиями.

Обычно вершины графа нумеруют последовательными натуральными числами от 1 до . Простым способом хранения графа является матрица смежности. Матрицей смежности графа G называется таблица A[1.., 1..] такая, что A[i, j] = 1, если граф G содержит ребро из вершины с номером i в вершину с номером j и A[i, j] = 0 в противном случае. Заметим, что на главной диагонали этой матрицы расположены нули и, если граф G – неориентированный, то эта матрица симметрична относительно главной диагонали. Иногда рассматривают взвешенные графы, в которых каждому ребру (a, b) ставится в соответствие число w(a, b), называемое весом ребра. При хранении таких графов также можно использовать матрицу смежности, при этом A[i, j] = w, если граф G содержит ребро из вершины с номером i в вершину с номером j веса w, и A[i, j] = 0, если граф не содержит ребра из вершины с номером i в вершину с номером j. Достоинством (одним из немногих) матрицы смежности является возможность получения информации о наличии или отсутствии заданного ребра в графе за время O(1). Действительно, достаточно только проверить, чему равна соответствующая ячейка матрицы A.

Серьезным недостатком матрицы смежности является то, что ее хранение требует использования O(2) байт памяти. В задачах часто встречаются разреженные графы, у которых величина гораздо меньше, чем . Матрица смежности таких графов содержит очень много нулей. В таких случаях хорошим выбором будет использование списков смежности. Будем хранить граф G при помощи массива Adj[1..]. При этом каждый его элемент Adj[i] представляет собой список всех ребер, выходящих из вершины с номером i. Такое представление графа расходует память экономнее: его использование требует всего байт памяти, что гораздо меньше для разреженных графов. Списки смежности также можно использовать для хранения взвешенных графов, при этом вес ребра хранится в элементе списка как дополнительная информация. Следует отметить, что при использовании списков смежности мы уже не можем определить за O(1) присутствие или отсутствие заданного ребра в графе. Теперь нам нужно просмотреть весь список ребер, выходящих из начальной вершины этого ребра, для чего (в худшем случае) может понадобиться времени. Однако большинство алгоритмов на графах не работают отдельно с каждым ребром. Обычно некоторый процесс производится или со всеми ребрами графа, или со всеми ребрами, выходящими из заданной вершины. И в том, и в другом случае списки смежности оказываются более эффективными чем матрица смежности. Иногда рассматривают графы, в которых может быть несколько ребер, соединяющих одну и ту же пару вершин. Такие графы называют мультиграфами. Списки смежности позволяют хранить такие графы, тогда как хранение мультиграфов при помощи матрицы смежности затруднительно (если, вообще, возможно).

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


Упражнение 3. Предположим, что граф необходимо также модифицировать, например, добавлять и удалять ребра. Сравните с этой позиции матрицу смежности и списки смежности.

Упражнение 4. Предположим, что граф не нужно модифицировать. Предложите способ хранения графа, обладающий всеми описанными выше достоинствами списков смежности и дополнительно позволящий проверять наличие или отсутствие заданного ребра за O(logE).


п2) Приоритетные очереди.


Иногда необходимо работать с динамически изменяющимся множеством объектов, среди которых часто нужно находить объект с минимальным ключом (будем полагать, что ключи – это числа). В этом случае может пригодиться структура данных, называемая “приоритетной очередью”. Более точно, приоритетная очередь – это структура, хранящая набор объектов и поддерживающая следующие операции:


INSERT (x) – добавляет в очередь новый объект x;

MINIMUM – возвращает объект с минимальным значением ключа (если таких несколько, то любой из них);

EXTRACT-MIN – удаляет из очереди объект с минимальным значением ключа (если таких несколько, то удаляется объект, возвращаемый операцией MINIMUM).


Этот пункт разделен на два раздела. В первом рассматривается реализация приоритетной очереди, называемая бинарной кучей. Эта реализация позволяет также удалять произвольные объекты из множества, а также менять значения ключей объектов (для выполнения этих операций, однако, необходимо знать информацию о позиции объекта, к которыму мы хотим их применить). Во втором разделе рассматривается два примера применения бинарной кучи.


а) ^ Бинарная куча


Будем считать, что объекты хранятся в вершинах полного двоичного дерева (самый нижний уровень дерева заполнен, возможно, не полностью).


3


2





4

5

6

7

9


8








1

10

11

12

Пронумеруем вершины этого дерева слева направо сверху вниз (см. рисунок). Пусть N – количество вершин в дереве. Нетрудно видеть, что справедливы следующие свойства.

Свойство 1. Высота полного двоичного дерева из N вершин (то есть максимальное количество ребер на пути от корня к листьям) есть O(log N).

Свойство 2. Рассмотрим вершину полного двоичного дерева из N вершин, имеющую номер i. Если i = 1, то у вершины i нет отца. Если i > 1, то ее отец имеет номер i div 2. Если 2i < N, то у вершины i есть два сына с номерами 2i и 2i+1. Если 2i = N, то единственный сын вершины i имеет номер 2i. Если 2i > N, то у вершины i нет сыновей.

Будем говорить что объекты, хранящиеся в дереве, образуют бинарную кучу, если ключ объекта, находящегося в любой вершине, всегда не превосходит ключей объектов в сыновьях этой вершины. Будем хранить бинарную кучу в массиве H. Элемент этого массива H[i] будет содержать объект, находящийся в вершине дерева с номером i.

Следующее очевидное свойство бинарной кучи является ключевым.

Свойство 3. В бинарной куче объект H[1] (или объект, хранящийся в корне дерева) имеет минимальное значение ключа из всех объектов.

Отсюда сразу же получается эффективная реализация операции MINIMUM, работающая за O(1).


Operation MINIMUM

Return H[1];

End;


Реализация остальных операций не столь очевидна. Рассмотрим операцию INSERT. Сначала мы помещаем добавляемый объект x на самый нижний уровень дерева на первое свободное место. Если окажется, что ключ этого объекта больше (или равен) ключа его отца, то свойство кучи нигде не нарушено, и мы корректно добавили вершину в кучу. В противном случае, поменяем местами объект с его отцом. В результате вершина с добавляемым объектом «всплывает» на одну позицию вверх. Это «всплытие» продолжается до тех пор, пока ключ объекта не станет больше (или равен) ключа его отца или пока объект не «всплывет» до самого корня дерева. Время работы операции INSERT прямо пропорционально высоте дерева. Как следует из Свойства 1, оно равно O(log N).


Operation INSERT (x)

N:= N+1;

H[N]:= x;

i:= N;

While (i > 1) and (H[i].Key < H[i div 2].Key) Do Begin

S:= H[i];

H[i]:= H[i div 2];

H[i div 2]:= S;

i:= i div 2;

End;

End;


Теперь рассмотрим операцию EXTRACT-MIN. Для ее реализации мы сначала перемещаем объект из листа с номером N в корень (при этом объект в корне затирается, так как его и нужно удалить). Ставший свободным при этом лист удаляется. Если теперь окажется, что ключ объекта в корне меньше (или равен) ключей объектов в его сыновьях (что очень маловероятно), то свойство кучи нигде не нарушено и удаление было проведено корректно. В противном случае, выберем сына корня с минимальным значением ключа и поменяем объект в корне с объектом в этом сыне. В результате объект, находившийся в корне, «спускается» на одну позицию вниз. Этот «спуск» продолжается до тех пор, пока объект не окажется в листе или его ключ не станет меньше (или равен) ключей объектов в его сыновьях. Операция выполняется за O(log N), так как время ее работы пропорционально высоте дерева.


Operation EXTRACT-MIN

H[1]:= H[N];

N:= N-1;

i:= 1;

While 2*i <= N Do Begin

If (2*i = N) or (H[2*i].Key < H[2*i+1].Key)

Then Min:= 2*i

Else Min:= 2*i+1;

If H[i].Key <= H[Min].Key

Then Break;

S:= H[i];

H[i]:= H[Min];

H[Min]:= S;

i:= Min;

End;

End;


Итак, мы эффективно реализовали приоритетную очередь на базе бинарной кучи. Рассмотрим теперь еще две операции, которые можно эффективно выполнять в бинарной куче:


CHANGE-KEY (i, k) – установить ключ объекта H[i] равным k;

DELETE (i) – удалить объект H[i] из кучи.


Для реализации операции CHANGE-KEY рассмотрим три варианта. Если H[i].Key > k, то ключ вершины i уменьшается и может нарушиться свойство кучи в ее отце. Аналогичная ситуация возникала в операции INSERT. В этом случае действуем точно так же – производим «всплытие» вершины. Если H[i].Key = k, то ключ вершины i не меняется и ничего делать не надо. Если, наконец, H[i].Key < k, то ключ вершины i увеличивается и в ней может нарушиться свойство кучи. Аналогичная ситуация возникала в операции DELETE. В этом случае нужно произвести «спуск» вершины. Во всех трех случаях время работы будет ограничено величиной O(logN).


Упражнение 5. Напишите псевдокод операции CHANGE-KEY.


Операцию DELETE можно написать следующим образом:


Operation DELETE (i)

CHANGE-KEY (i, H[1].Key-1);

EXTRACT-MIN;

End;


После выполнения CHANGE-KEY объект, находившийся в H[i], будет иметь минимальное значение ключа среди всех объектов, после чего будет удален при помощи вызова EXTRACT-MIN. Время работы операции равно O(logN).


Упражнение 6. Пусть массив H содержит N объектов, но не является кучей. Опишите способ превратить его в кучу за линейное время O(N).


б) Примеры.


Пример 1. Рассмотрим следующую задачу HUMBLE. Предположим, что задано множество P = {p1, p2, …, pk}, где все pi – попарно различные простые числа. Рассмотрим множество M, состоящее из тех чисел, в разложении которых на простые множители нет чисел, отличных от pi. То есть в M входят все числа вида p1a1p2a2…pkak, ai 0. Необходимо вывести N минимальных чисел из множества M в порядке возрастания. Будем предполагать, что числа на входе и выходе этой задачи помещаются в некоторый стандартный целочисленный тип и все арифметические операции над ними выполняются за O(1). Опишем решение этой задачи, работающее за O(NlogN+KlogK), причем расходы памяти составят порядка O(N+K) байт.

Мы предполагаем здесь, что числа pi отсортированы по возрастанию (в противном случае их можно отсортировать за O(KlogK)). Для решения будет использоваться приоритетная очередь, реализованная при помощи бинарной кучи. Каждый объект, хранящийся в очереди, будет соответствовать некоторому числу из множества M. Ключ объекта как раз и будет равен значению числа. Кроме этого, в объекте хранится дополнительная информация – номер максимального простого числа, входящего в разложение ключа объекта на простые множители. Итак, для каждого объекта obj, хранящегося в очереди, имеем: pobj.Data – максимальное число в разложении obj.Key на простые множители.

Наш алгоритм будет работать по шагам. На каждом шаге некоторый объект будет доставаться из кучи. Его ключ и будет очередным выводимым числом. Далее некоторые новые объекты, которые могут вывестись на следующих шагах, будут помещаться в кучу. Сейчас необходимо решить, какие именно объекты мы будем помещать в кучу на каждом шаге.

Самый простой вариант заключается в следующем: когда мы достаем из кучи объект с ключом X, то можно поместить в кучу объекты с ключами Xp1, Xp2, …, Xpk. Этот вариант далек от идеала по двум причинам. Первая состоит в том, что объект с одним и тем же ключом может быть помещен в кучу несколько раз (например, объект с ключом p1p2 будет помещен в кучу, когда мы достаем из нее объект с ключом p1 и объект с ключом p2). Если бы даже этого не было, то возникает вторая проблема: во время работы алгоритма нам нужно сделать порядка O(NK) добавлений элементов в кучу, что недопустимо как по причинам, связанным со временем работы, так и по причинам, связанным с памятью.

Решим сначала проблему с повторами в куче. Для этого вспомним, что мы пока никак не используем дополнительную информацию, хранящуюся в объектах. Новое наше правило выглядит следующим образом: когда мы достаем из кучи объект с ключом X и дополнительной информацией t, то будем помещать в кучу объекты с ключами Xpt, Xpt+1, …, Xpk. Теперь наличие одинаковых объектов в куче исключено и мы можем оценить сложность решения. Нетрудно видеть, что она равна O(NKlog(NK)), а расходы памяти составляют O(NK) байт.

Для улучшения решения, неплохо бы придумать такое правило добавления новых объектов в кучу, при котором на каждом шаге добавляется некоторое постоянное (не зависящее от N или K) количество объектов. Рассмотрим следующие две унарные операции A и B над объектами. В результате действия операции A из объекта obj получается объект с ключом obj.Keypobj.Data и дополнительной информацией obj.Data. В результате действия операции A из объекта obj получается объект с ключом obj.Key/pobj.Datapobj.Data+1 и дополнительной информацией obj.Data+1 (предполагается, что obj.Data < k). Наш алгоритм основан на следующих свойствах введенных операций.

Свойство 1. Начиная с объекта с ключом p1 с помощью применения конечного числа операций A и B в некотором порядке можно получить объект с ключом, равным какому угодно числу из множества M.

Свойство 2. В результате действия операций A и B ключ объекта увеличивается.

Свойство 3. Любой объект X (кроме объекта с ключом p1) может быть получен из некоторого объекта Y применением операции A или B. При этом, если X получен из Y применением операции A, то не существует объекта Z такого, что X получается из Z применением операции B. Аналогично, если X получен из Y применением операции B, то не существует объекта Z такого, что X получается из Z применением операции A. (Ключи всех рассматриваемых объектов принадлежат множеству M).

Окончательный вариант используемого правила таков: доставая из кучи объект с ключом X, будем помещать в нее объекты, получаемые из X применением операций A и B. При этом свойство 1 гарантирует, что каждое число из M будет когда-нибудь выведено. Свойство 2 гарантирует, что числа будут выводиться в порядке возрастания. Наконец, свойство 3 исключает возможность появления повторов в приоритетной очереди.

Псевдокод полученного алгоритма выглядит следующим образом:


Algorithm HUMBLE

INIT-HEAP;

obj.Key:= p[1];

obj.Data:= 1;

INSERT (obj);

For i:= 1 to N Do Begin

minobj:= MINIMUM;

EXTRACT-MIN;

OUTPUT(minobj.Key);

obj.Key:= minobj.Key*p[minobj.Data];

obj.Data:= minobj.Data;

INSERT (obj);

If minobj.Data < N

Then Begin

obj.Key:= (minobj.Key div p[minobj.Data])*p[minobj.Data+1];

obj.Data:= minobj.Data+1;

INSERT (obj);

End;

End;

End;


Нетрудно видеть, что время работы полученного алгоритма (с учетом времени на сортировку массива p), равно O(NlogN+KlogK). Так как общее количество добавлений в кучу не превышает 2N, то для нее необходимо O(N) байт памяти, и общие расходы памяти составят O(N+K) байт.

Упражнение 7. Проведите строгое доказательство свойств 1-3 и объясните подробнее, почему их выполнение гарантирует корректность работы приведенного алгоритма.


В примере 1 мы использовали только те операции, которые допустимы в приоритетной очереди. Но, как говорилось в предыдущем разделе, в бинарной куче можно эффективно выполнять еще и операции CHANGE-KEY и DELETE. Следующий пример иллюстрирует полезность операции CHANGE-KEY.


Пример 2. Рассмотрим следующую задачу THERACE. На координатной прямой в точках с координатами X1, X2, …, XN расположены N точек. Для простоты будем предполагать, что X1 < X2 < … < XN. В момент времени 0 каждая точка, имеющая координату Xi, начинает двигаться вправо с постоянной скоростью Vi > 0. В некоторые моменты времени одна из точек может “обогнать” другую. Будем считать, что никакие два «обгона» не происходят одновременно. Упорядочим все обгоны по возрастанию момента времени, в которые они происходят. Вывести информацию о первых K произошедших обгонах (предполагается, что K не превосходит общего числа обгонов). Для каждого обгона вывести, какая точка обгоняет какую. Мы рассмотрим решение этой задачи, имеющее сложность O((N+K)logN) и использующее порядка O(N) байт памяти.

Для упрощения дальнейших рассуждений введем фиктивную точку с номером N+1, которая находится где-то очень далеко справа и движется очень быстро, и точку с номером 0, которая находится где-то очень далеко слева и движется очень медленно. Следующая простая функция TIME (i, j) выдает момент времени, когда i-я точка обгоняет j-ю (предполагается, что 1  i, j  N+1). Если такого не может произойти никогда, то возвращается специальное значение INFINITY (бесконечность). Мы считаем, что бесконечность больше любого конечного числа.


Function TIME (i, j)

If (i = N+1) or (j = N+1)

Then Return INFINITY

Else

If (X[i] < X[j]) and (V[i] > V[j])

Then Return (X[j]-X[i])/(V[i]-V[j])

Else

If (X[j] < X[i]) and (V[j] > V[i])

Then Return (X[i]-X[j])/(V[j]-V[i])

Else Return INFINITY;

End;


Наш алгоритм будет работать с бинарной кучей. В каждый момент времени будет находиться ровно N объектов. Каждый объект соответствует некоторой точке. Для каждого объекта мы храним следующую дополнительную информацию: поле Id, равное номеру точки, которой соответствует объект; поле Next, равное номеру точки, которая в рассматриваемый момент времени является ближайшей справа от точки Id; поле Prev, равное номеру точки, которая в рассматриваемый момент времени является ближайшей слева от точки Id (поля Next и Prev могут принимать фиктивные значения 0 и N+1). Что касается ключа объекта, то он равен моменту времени, когда точка Id обгонит точку Next (возможно, что ключ равен INFINITY). Кроме кучи мы будем также поддерживать массив Pos[1..N], обладающий следующим свойством: H[Pos[i]].Id = i. То есть, Pos[i] хранит местоположение в куче того объекта, поле Id у которого равно i. Здесь мы существенно используем то, что значение поля Id – целое число от 1 до N, и никакие два объекта не могут иметь одинаковое значение этого поля.


Упражнение 8. Покажите, как можно модифицировать операции для работы с кучей, так, чтобы ассимптотическое время работы этих операций осталось неизменным, и кроме этого всегда поддерживались правильные значения элементов массива Pos.


Основная идея нашего алгоритма очень проста: когда точка с номером i обгоняет точку с номером j, то чуть-чуть раньше этого момента эти две точки были соседями. Следовательно, для того, чтобы получить информацию об очередном обгоне, необходимо взять из кучи объект obj с минимальным ключом. Из него мы узнаем, что на очередном обгоне точка с номером obj.Id обгоняет точку с номером obj.Next. После этого обгона расположение точек на прямой немного изменится и нужно модифицировать некоторые поля некоторых объектов в куче и переходить к следующему обгону. Так мы делаем K раз. Рассмотрим псевдокод получившегося алгоритма.


Algorithm THERACE

INIT-HEAP;

For i:= 1 to N Do Begin

obj.Id:= i;

obj.Next:= i+1;

obj.Prev:= i-1;

obj.Key:= TIME (obj.Id, obj.Next);

INSERT (obj);

End;

For i:= 1 to K Do Begin

minobj:= MINIMUM;

OUTPUT (minobj.Id, minobj.Next);

H[Pos[minobj.Id]].Prev:= minobj.Next;

H[Pos[minobj.Id]].Next:= H[Pos[minobj.Next]].Next;

H[Pos[minobj.Next]].Prev:= minobj.Prev;

H[Pos[minobj.Next]].Next:= minobj.Id;

If H[Pos[minobj.Id]].Next <> N+1

Then H[Pos[H[Pos[minobj.Id]].Next]].Prev:= minobj.Id;

If minobj.Prev <> 0

Then Begin

H[Pos[minobj.Prev]].Next:= minobj.Next;

CHANGE-KEY (Pos[minobj.Prev], TIME (H[Pos[minobj.Prev]].Id, H[Pos[minobj.Prev].Next]);

End;

CHANGE-KEY (Pos[minobj.Id], TIME (H[Pos[minobj.Id]].Id, H[Pos[minobj.Id]].Next);

CHANGE-KEY (Pos[minobj.Next], TIME (H[Pos[minobj.Next]].Id, H[Pos[minobj.Next]].Next);

End;

End;


Очевидно, что время работы приведенного алгоритма составляет O((N+K)logN) и мы используем порядка O(N) байт памяти.


Упражнение 9. Предложите алгоритм, считающий общее число обгонов, которые произойдут, за время O(NlogN). Возможно, Вам помогут идеи из пункта 4, но есть и алгоритм, не использующий этих идей, а основанный на подходе «разделяй и властвуй».


п3) Система непересекающихся множеств.


В некоторых задачах необходимо хранить разбиение какого-то набора объектов на непересекающиеся множества и уметь эффективно выполнять следующие операции:


FINDSET (x) – возвращает идентификатор множества, содержащего объект x (под идентификатором мы понимаем уникальное число определяющее множество);

UNION (a, b) – объединяет множества с идентификаторами a и b в одно (предполагается, что ab).


Структуру данных, умеющую выполнять такие операции, назовем системой непересекающихся множеств. Далее мы предполагаем, что объекты пронумерованы от 1 до N и операция FINDSET вместо объекта x получает на вход его номер, так что система непересекающихся множеств непосредственно с объектами работать не будет. В дальнейшем, мы отождествляем объекты с их номерами. Будем считать, что в начальный момент времени каждый объект находится в отдельном множестве. В связи с этим мы также рассматриваем еще одну операцию, которая применяется только один раз и инициализирует систему непересекающихся множеств:


INIT (N) – инициализировать систему непересекающихся множеств, поместив в нее набор из N непересекающихся множеств – по одному множеству для каждого объекта.


Мы рассматриваем разные реализации системы непересекающихся множеств. В некоторых реализациях время работы каждой операции может быть достаточно точно оценено. В других реализациях мы будем рассматривать оценку такого рода: чему равно время выполнения произвольного набора из M операций (FINDSET и UNION), после того как она была инициализирована вызовом INIT (N)?


Пункт разделен на 4 раздела. Первые три из них посвящены реализации системы непересекающихся множеств на основе массивов, списков и леса. В последнем разделе рассматривается пример задачи, эффективно решаемой с помощью такой структуры данных.


а) ^ Реализация на основе массива.


Эта реализация является идейно очень простой, однако очень неэффективной по времени. Идея заключается в том, чтобы хранить некоторый массив Pr[1..N], в котором для каждого объекта i хранится значение представителя множества, в котором этот объект находится. Итак, Pr[i] – представитель множества, содержащего объект i. Реализация всех операций при этом очевидна и приводится без комментариев.


Operation INIT (N)

For i:= 1 to N Do

Pr[i]:= i;

End;


Operation FINDSET (x)

Return Pr[x];

End;


Operation UNION (a, b)

For i:= 1 to N Do

If Pr[i] = a

Then Pr[i]:= b;

End;


Оценим время работы каждой из операций. Операция INIT работает за O(N), операция FINDSET – за O(1), операция UNION – за O(N). Серьезный недостаток – долгое время работы операции UNION (то, что INIT работает долго – не страшно, так как она вызывается всего один раз). Так как общее количество операций UNION не превосходит N-1 (после каждой из них общее количество множеств уменьшается), то получаем также следующий результат: после того, как был произведен вызов INIT (N), суммарное время работы любой последовательности из M операций не превосходит O(N2+M). Вывод таков: полученная реализация крайне неэффективна, однако для небольших значений N и M она хороша вследствие своей простоты.


б) ^ Реализация на основе списков


Более эффективная реализация получится, если хранить объекты (их номера) каждого множества в некотором списке. Опишем ее более подробно. Для хранения списков мы используем массив Next[1..N], смысл которого таков: если объект i является последним в своем списке, то Next[i] = 0, иначе Next[i] равен номеру объекта, который является следующим в списке за i. Как и раньше, мы сохраняем массив Pr, хранящий представителей. Теперь мы добавляем еще одно условие: представителем каждого множества является объект, находящийся в начале списка, которым представлено это множество. Кроме этого, мы используем массив L[1..N], где L[i] – длина (количество элементов) в списке, содержащем объект i. Наконец, нам понадобится массив Tail[1..N], в котором Tail[i] равен последнему элементу списка, содержащего элемент i. Однако мы заботимся о правильности значений L[i] и Tail[i], только если i – представитель какого-нибудь множества.

Перейдем к реализации операций. Операция INIT просто помещает каждый объект в отдельный список и работает за O(N).


Operation INIT (N)

For i:= 1 to N Do Begin

Next[i]:= 0;

Pr[i]:= i;

Tail[i]:= i;

L[i]:= 1;

End;

End;


Операция FINDSET остается прежней и работает за O(1).


Operation FINDSET (x)

Return Pr[x];

End;


Для реализации операции UNION нужно присоединить хвост одного из списков к голове второго, далее везде во втором списке поменять представителей, и, наконец, изменить длину первого списка. Так как время работы операции получается пропорциональной длине второго списка, то имеет смысл в качестве первого списка выбирать более длинный из двух объединяемых, а в качестве второго – менее длинный. Как мы увидим дальше, именно эта идея поможет нам добиться выигрыша.


Operation UNION (a, b)

If L[a] < L[b]

Then Begin

s:= a;

a:= b;

b:= s;

End;

Next[Tail[a]]:= b;

Tail[a]:= Tail[b];

L[a]:= L[a]+L[b];

x:= b;

While x <> 0 Do Begin

Pr[x]:= a;

x:= Next[x];

End;

End;


Как уже говорилось, время работы операции операции UNION есть O(min{L[a], L[b]}) и в худшем случае оно составляет O(N). Однако, как показывает следующая теорема, в среднем это время невелико (порядка O(logN)).


Теорема 1. Если система непересекающихся множеств реализована на основе списков, то после вызова INIT (N) суммарное время работы любой последовательности из M операций не превосходит O(NlogN+M).

Доказательство. Суммарное время работы всех операций FINDSET из э
еще рефераты
Еще работы по разное