Приоритетная очередь — это абстрактный тип данных, предназначенный для представления взвешенных множеств. Множество называется взвешенным, если каждому его элементу однозначно соответствует число, называемое ключом или весом. Основными операциями над приоритетной очередью являются следующие операции:
Дополнительные операции над приоритетными очередями:
Приоритетная очередь естественным образом используется в таких задачах, как сортировка элементов массива, поиск во взвешенном неориентированном графе минимального остовного дерева, поиск кратчайших путей от заданной вершины взвешенного графа до его остальных вершин, и во многих других.
Приоритетную очередь можно представить с помощью массива или списка элементов, но такие реализации неэффективны по времени выполнения основных операций. Так, например, поиск элемента с минимальным ключом в неупорядоченном массиве или списке требует последовательного просмотра всех его элементов. Если поддерживать упорядоченность массива или списка по ключу, то "неудобной" окажется операция вставки нового элемента.
Чаще всего приоритетная очередь представляется с помощью
Соответствие между узлами дерева и элементами множества называется кучеобразным, если для каждого узла $$i$$ соблюдается следующее условие:
Ключ элемента, приписанного узлу $$i$$, не превосходит ключей, приписанных его потомкам.
Такие представления взвешенных множеств называются
Представление приоритетной очереди с помощью $$d$$ -кучи основано на использовании так называемых завершенных $$d$$ -арных деревьев ( $${d \ge 2}$$ ).
Завершенное $$d$$ -арное дерево — это корневое дерево со следующими свойствами:
Узлы завершенного $$d$$ -арного дерева принято нумеровать следующим образом: корень получает номер 0, потомки узла с номером $$i$$ получают номера: $$i\cdot d + 1$$, $$i\cdot d + 2$$, $$\ldots$$, $$i\cdot d + d$$. Такая нумерация удобна тем, что позволяет разместить узлы дерева в массиве в порядке возрастания их номеров, при этом позиции потомков любого узла в массиве легко вычисляются по позиции самого узла. Так же легко по позиции узла вычислить позицию его родителя. Так, для узла, расположенного в позиции $$i$$, родительский узел располагается в позиции $$(i - 1) \mathop{\rm div} d$$, где $$\mathop{\rm div}$$ — операция деления нацело.
В изображении завершенного $$d$$ -арного дерева узлы одинаковой глубины удобно располагать на одном уровне, при этом потомки одного узла располагаются слева направо в порядке объявленных номеров. При таком рисовании нижний уровень заполняется, возможно, не полностью.
Отметим некоторые простые утверждения о завершенных $$d$$ -арных деревьях, которые будут полезны при анализе трудоемкости основных операций.
Утверждение 1. Длина $$h$$ пути из корня завершенного $$d$$ -арного дерева с $$n > 1$$ узлами в любой лист удовлетворяет неравенствам:$$\eq*{ \log_d n - 1 < h < \log_d n + 1. }$$
Доказательство Минимальное количество узлов в $$d$$ -куче высоты $$h$$ ( $$h > 0$$ ), по свойствам 2 и 3 $$d$$ -арного дерева, очевидно, равно $$1 + d + d^2 + \ldots + d^{h - 1} + 1$$ (последний уровень содержит лишь один узел).
Максимальное количество узлов в такой $$d$$ -куче равно $$1 + d + d^2 + \ldots + d^h$$ (последний уровень содержит $$d^h$$ узлов). Отсюда имеем неравенства:$$\eq*{ (1 + d + d^2 + \ldots + d^h - 1 + 1) \le n \le (1 + d + d^2 + \ldots + d^h). }$$
Суммируя левую и правую части как геометрические прогрессии, получим$$\eq*{ (d^h - 1)/(d - 1) + 1 \le n \le (d^{h + 1} - 1)/(d - 1), }$$ и после некоторых очевидных оценок с помощью логарифмирования получаем требуемые неравенства:$$\eq*{ \log_d n - 1 < h < \log_d n + 1. }$$
Утверждение 2. Количество узлов высоты $$h$$ не превосходит $$n/d^h$$.
Под высотой узла понимается расстояние от него до наиболее далекого потомка. Кучу, содержащую $$n$$ элементов, будем представлять двумя массивами — $$a[0 \ldots n - 1]$$ и $${\rm key}[0 \ldots n - 1]$$, — полагая что $$a[i]$$ — имя элемента, приписанного узлу $$i$$ ; $${\rm key}[i]$$ — его ключ. Иногда под $$a[i]$$ удобно понимать сам элемент исходного множества или ссылку на него. В некоторых прикладных задачах нет необходимости помещать в приоритетную очередь ни сами элементы, ни их имена, в таких случаях при организации кучи используется лишь массив $${\rm key}[0 \ldots n - 1]$$.
На рис. 4.1 приведен пример кучи для $$d = 3$$, $$n = 18$$. Кружочками изображены узлы дерева, в них записаны элементы массива, представляющие имена элементов кучи.
Пример кучи при $$d = 3$$, $$n = 7$$ для приоритетной очереди, содержащей элементы с ключами $$1, 2, 2, 2, 3, 4, 5$$, изображен на рис. 4.2, где пара чисел в каждом кружочке обозначает номер узла и ключ соответствующего элемента.
(рис 4.2) (рис 4.1) При реализации основных операций над кучами используются две вспомогательные операции — ВСПЛЫТИЕ и ПОГРУЖЕНИЕ. При реализации этих операций введем еще одну вспомогательную операцию — транспонирование, с помощью которой будем менять местами элементы, расположенные в двух разных узлах дерева. Ее реализация может быть представлена следующим образом:
$$\formula{ \t{procedure}\ tr(i, j);\\ \t begin\\ \mbox{}\q {\rm temp}0:= a[i]; a[i]:= a[j];\ a[j]:= {\rm temp}0; \\ \mbox{}\q {\rm temp}1:= {\rm key}[i];\ {\rm key}[i]:= {\rm key}[j];\ {\rm key}[j]:= {\rm temp}1;\\ \t end; }$$Замечание. Если в кучу помещаются только ключи элементов, то процедура транспонирования модифицируется соответствующим образом.
Операция ВСПЛЫТИЕ.Эта операция применяется в тех случаях, когда в некотором узле, например в $$i$$ -м, расположен элемент $$x$$, нарушающий кучеобразный порядок так, что его ключ меньше ключа его родителя $$y$$.
Элементы $$x$$ и $$y$$ меняются местами. Если после этого элемент $$x$$ снова не удовлетворяет условиям кучи, то еще раз проводится аналогичная перестановка. И так до тех пор, пока $$x$$ не встанет на свое место.
Рассмотрим 3-дерево на рис. 4.3. В этом дереве кучеобразный порядок нарушает узел $$17$$ с ключом $$14$$, так как его родительскому узлу приписан элемент с ключом $$31 > 14$$.
(рис 4.3) Применим к узлу $$17$$ операцию ВСПЛЫТИЕ. Элементы с ключами $$31$$ и $$14$$ меняются местами. В результате получается дерево, представленное на рис. 4.4.
(рис 4.4) Теперь нарушен кучеобразный порядок в узле $$5$$ ( $$21 > 14$$ ), меняем местами элементы c ключами $$21$$ и $$14$$. В результате получаем кучу, изображенную на рис. 4.5. Кучеобразный порядок восстановлен, операция ВСПЛЫТИЕ завершена.
(рис 4.5) Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Это число, очевидно, не более чем удвоенное число узлов в пути от узла $$x$$ до корня дерева. Длина такого пути в $$d$$ -куче с $$n$$ узлами не превосходит ее высоты, а именно $$\log_d n + 1$$, в соответствии с доказанным выше утверждением 1. Значит, время выполнения данной операции — $$O(\log_d n)$$.
Реализация операции ВСПЛЫТИЕ. Входным параметром этой операции является номер узла, в котором нарушен порядок:
$$\formula{ \t{procedure ВСПЛЫТИЕ}(i);\\ \t{begin}\\ p:= (i - 1)\ \t div\ d;\\ \mbox{}\q\t while (i \ne 0)\ \t and\ ({\rm key}[p] > {\rm key}[i])\ \t do\ \{{\rm tr}(i, p);\ i:= p;\ p:= (i - 1)\ \t div\ d\};\\ \t end; }$$Замечание.
Операция ПОГРУЖЕНИЕ. Эта операция также применяется для восстановления свойства кучеобразности. Пусть, например, в $$i$$ -м узле расположен элемент $$x$$, нарушающий кучеобразный порядок таким образом, что ключ элемента $$x$$ больше ключа элемента $$y$$, приписанного потомку узла $$i$$. В этом случае среди непосредственных потомков узла $$i$$ выбирается элемент $$y$$ с наименьшим ключом, и элементы $$x$$ и $$y$$ меняются местами. Если после этого элемент $$x$$ снова не удовлетворяет условиям кучи, то еще раз проводим аналогичную перестановку. И так до тех пор, пока $$x$$ не встанет на свое место.
Рассмотрим $$3$$ -дерево, представленное на рис. 4.6. В узле $$1$$ расположен элемент $$x$$ с ключом $$31$$, и этот узел имеет двух потомков с меньшими ключами, а именно $$30$$ и $$14$$. Применим к элементу $$x$$ операцию ПОГРУЖЕНИЕ.
(рис 4.6) Среди непосредственных потомков узла 1 находим узел, которому приписан элемент $$y$$ с наименьшим ключом, в нашем случае это узел $$5$$ c ключом $$14$$. Меняем местами элементы $$x$$ и $$y$$. В результате получается дерево, изображенное на рис. 4.7.
(рис 4.7) Теперь элемент $$x$$ снова имеет потомка с меньшим, чем у него, ключом (а точнее, оба его потомка имеют меньшие ключи). Снова находим непосредственного потомка элемента $$x$$ с наименьшим ключом, и меняем его и $$x$$ местами. Получается дерево, изображенное на рис. 4.8.
(рис 4.8) Теперь $$x$$ находится в узле 17 и не имеет потомков с меньшим, чем у него, ключом (точнее, у него вообще нет потомков). Операция ПОГРУЖЕНИЕ завершена.
Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Для каждого узла в пути следования данной операции производится $$d$$ сравнений (при поиске потомка с минимальным ключом) и один обмен. Длина этого пути в $$d$$ -куче с $$n$$ узлами не превосходит ее высоты, а именно $$\log_d n$$, по доказанному выше утверждению 1. Значит, время выполнения данной операции — $$O(d\cdot \log_d n)$$.
Для реализации операции погружения воспользуемся функцией $${\rm minchild} (i)$$, позволяющей для любого узла $$i$$ находить его непосредственного потомка с минимальным ключом. Если у узла $$i$$ нет потомков, то $${\rm minchild} (i) = 0$$.
Реализация операции ПОГРУЖЕНИЕ
$$\formula{ \t{procedure ПОГРУЖЕНИЕ}(i);\\ \t begin \\ \mbox{}\q c:= {\rm minchild}(i);\\ \mbox{}\q \t while\ (c \ne 0)\ \t and\ ({\rm key}[c] < {\rm key}[i])\ \t do\ \{{\rm tr}(i, c);\ i:= c;\ c := {\rm minchild} (c)\}\\ \t end; }$$ $$\formula{ \t function\ {\rm minchild} (i);\\ \t begin\ \t if\ i\cdot d + 1 > n\ \t then\ {\rm minchild} := 0\ \t else\\ \mbox{}\q \t begin\\ \mbox{}\q\qq {\rm first\_child}:= i\cdot d + 1;\ {\rm last\_child}:= \min((i + 1)\cdot d - 1, n);\\ \mbox{}\q\qq{\rm min\_key} := {\rm key}[{\rm first\_child}];\\ \mbox{}\q\qq \t for\ i := {\rm first\_child}\ \t to\ {\rm last\_child}\ \t do\ \t if\ {\rm key}[i] > {\rm min\_key}\ \t then\\ \mbox{}\q\qq\qq \{{\rm min\_key} := {\rm key}[i];\ {\rm minchild} := i\}\\ \mbox{}\q \t end\\ \t end }$$Операция ВСТАВКА. Если перед выполнением этой операции куча содержала $$n$$ узлов (напомним, что они пронумерованы числами от $$0$$ до $${n - 1}$$ ), то добавляем к дереву $$(n + 1)$$ -й узел (его номер будет $$n$$ ) и приписываем ему элемент с именем $${\rm name}X$$ и ключом $${\rm key}X$$. Вставка нового элемента производится посредством отведения для него места в $$n$$ -ых позициях массивов $$a$$ и $${\rm key}$$ соответственно, после чего к добавленному узлу применяется операция ВСПЛЫТИЕ для восстановления кучеобразного порядка.
Вставим в $$d$$ -кучу, изображенную на рис. 4.9, новый элемент с ключом $$14$$.
(рис 4.9) Сначала добавляем к дереву новый узел с номером $$17$$ и приписываем ему элемент с ключом $$14$$. Получим дерево, представленное на рис. 4.10.
(рис 4.10) Затем применяем к узлу $$17$$ операцию ВСПЛЫТИЕ. При описании этой операции использовался именно приведенный пример (см. рис. 4.3, 4.4, 4.5).
Вычислительная сложность данной операции равна константе плюс вычислительная сложность операции ВСПЛЫТИЕ, то есть $$O(\log_d n)$$.
Реализация операции ВСТАВКА
$$\formula{ \t{procedure ВСТАВКА}\ ({\rm name}X, {\rm key}X);\\ \t begin\ {a}[{n}]:= {\rm name}X; {\rm key}[{n}]:= {\rm key}X;\ \t{ВСПЛЫТИЕ}\ ({n});\ {n}:= {n} + 1\ \t end; }$$Операция УДАЛЕНИЕ. Используется для удаления элемента, приписанного узлу с заданным номером $$i$$. Сначала элемент, приписанный последнему узлу дерева, переносится на место удаляемого элемента, последний узел при этом становится ненужным и поэтому удаляется из дерева. Далее, если узел $$i$$, в который помещен новый элемент, имеет родителя с большим ключом, то к узлу $$i$$ применяется операция ВСПЛЫТИЕ, в противном случае — ПОГРУЖЕНИЕ.
Таким образом, ориентируясь на худший случай, вычислительную сложность операции УДАЛЕНИЕ оцениваем величиной $$O(d\cdot \log_d n)$$.
Реализация операции УДАЛЕНИЕ
$$\formula{ \t{procedure УДАЛЕНИЕ}(i);\\ \t begin\ {a}[{i}]:= {a}[{n} - 1];\ {\rm key}[{i}]:= {\rm key}[{n} - 1];\ {n}:= {n} - 1; \\ \mbox{}\q \t if\ i \ne 0\ \t and\ {\rm key}[{i}] ({\rm key}[(i - 1) \mathop{\rm div} {d}]\ \t then\ \t{ВСПЛЫТИЕ}({i})\\ \mbox{}\q \t else\ \t{ПОГРУЖЕНИЕ}({i})\\ \t end; }$$Операция УДАЛЕНИЕ_МИНИМУМА. Эта операция предназначена для взятия из кучи элемента с минимальным ключом (он находится в корне дерева) и удаления его из кучи с помощью операции УДАЛЕНИЕ.
Реализация операции УДАЛЕНИЕ_МИНИМУМА
$$\formula{ \t{procedure УДАЛЕНИЕ\_МИНИМУМА}\ ({\rm name}X, {\rm key}X);\\ \t begin\ {\rm name}X:= {a}[0];\ {\rm key}X:= {\rm key}[0];\ \t{УДАЛЕНИЕ}\ (0)\ \t end; }$$Функция MINKEY. Эта функция предназначена для определения минимального ключа без удаления соответствующего элемента.
Реализация функции MINKEY
$$\formula{ \t function\ {\rm MINKEY};\ \t begin\ {\rm MINKEY}: = {\rm key}[0]\ \t end; }$$Трудоемкость операции, очевидно, равна $${O}(1)$$.
Операция УМЕНЬШЕНИЕ_КЛЮЧА. Предназначена для
Вычислительная сложность данной операции определяется временем,
затрачиваемым на
Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА
$$\formula{ \t{procedure УМЕНЬШИТЬ\_КЛЮЧ}\ (i, delta);\\ \t begin\ {\rm key}[{i}] := {\rm key}[{i}] - {delta};\ \t{ВСПЛЫТИЕ}\ (i);\ \t end; }$$
Операция ОКУЧИВАНИЕ. Заметим, что если $$d$$ -куча создается путем $$n$$ -кратного применения операции ВСТАВКА, то суммарная трудоемкость ее создания будет равна $$O(n\cdot \log_d n)$$. Если же все $$n$$ элементов сначала занимают в произвольном порядке массив $$a[0 \ldots (n - 1)]$$ и, соответственно, массив $${\rm key}[0 \ldots ({n} - 1)]$$, то можно превратить их в $$d$$ -кучу, применяя операцию ПОГРУЖЕНИЕ по очереди к узлам $$(n - 1),\,(n - 2),\,\ldots,\,0$$.
Такой процесс будем называть окучиванием массива. Для доказательства того, что в результате действительно устанавливается кучеобразный порядок, достаточно заметить, что если поддеревья с корнями в узлах $$n - 1,\, n - 2,\, \ldots,\, i + 1$$ упорядочены по правилу кучи, то после применения процедуры ПОГРУЖЕНИЕ к узлу $$i$$ поддерево с корнем в этом узле также станет упорядоченным по правилу кучи. Итак, остановимся на следующей реализации.
Реализация операции ОКУЧИВАНИЕ
$$\formula{ \t{procedure ОКУЧИВАНИЕ};\\ \t begin\\ \mbox{}\q \t for\ i:= n - 1\ \t downto\ 0\ \t do\ \t{ПОГРУЖЕНИЕ}\ (i)\\ \t end; }$$Утверждение 3. Вычислительная сложность операции ОКУЧИВАНИЕ равна $$O(n)$$.
Доказательство Заметим, что трудоемкость погружения с высоты $$h$$ равна $$O(h)$$, а количество узлов высоты $$h$$ не превосходит $$n/d^h$$. Осталось оценить сумму$$\eq*{ \suml_{h=1}^{H} h\frac{n}{d^{h}}, }$$ где $$H = \lceil \log_d n\rceil$$, и убедиться, что полученная сумма есть $$O(n)$$.
Для суммирования можно воспользоваться формулой$$\eq*{ \suml_{i=1}^k \frac{i}{x^i} = \frac{x^{k+1} - (k-1) x + k}{x^k (x-1)^2}. }$$
Предоставляем читателю возможность завершить доказательство.
Операция СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ. Эта операция применяется для получения списка элементов, которые имеют ключи, меньшие заданного значения $${\rm key}0$$, и реализуется следующим образом. Если ключ элемента, находящегося в корне, больше, чем $${\rm key}0$$, то это дерево не имеет искомых элементов. В противном случае включаем его в выходной список $$S$$, а затем применяем ту же процедуру ко всем потомкам узла, включенного в список.
Пусть куча содержит $$k$$ элементов с ключами, меньшими, чем $${\rm key}0$$. По свойству кучи, они все расположены на ее "верхушке". Данная процедура обходит эту верхушку за время, пропорциональное $$k$$, и для каждого из этих $$k$$ элементов просматривает все его $$d$$ (или меньше) непосредственных потомков. Получаем, что время выполнения данной процедуры является величиной $$O(d\cdot k)$$.
Реализация операции СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ
$$\formula{ \t{procedure СОЗДАТЬ\_СПИСОК\_МИНИМАЛЬНЫХ}(S, {\rm key}0);\\ \t begin\\ \mbox{}\q \t{Инициализируем пустой список} S; \\ \mbox{}\q \t{Инициализируем стек};\\ \mbox{}\q 0 \Rightarrow \t{стек};\\ \mbox{}\q \t{ while стек не пуст do}\\ \mbox{}\q\qq \t{begin стек} \Rightarrow i;\\ \mbox{}\q\qq\qq if ({\rm key}[i] < {\rm key}0)\ \t{then Добавить} a[i]\ \t{к списку}\ S;\\ \mbox{}\q\qq\qq \t for\ j:=d^\ast i + 1\ \t to\ d^\ast(i + 1)\ \t do if\ j \le (n - 1)\ \t then\ j \Rightarrow \t{стек};\\ \mbox{}\q\qq \t end\\ \t end }$$
Сводные данные о трудоемкости операций с d-кучами
| ВСПЛЫТИЕ $$(i)$$ | $$O(\log_d n)$$ |
| ПОГРУЖЕНИЕ $$(i)$$ | $$O(d \log_d n)$$ |
| ВСТАВКА $$({\rm name}X, {\rm key}X)$$ | $$O(\log_d n)$$ |
| УДАЛЕНИЕ $$(i)$$ | $$O(d \log_d n)$$ |
| УДАЛЕНИЕ_МИН $$({\rm name}X, {\rm key}X)$$ | $$O(d \log_d n)$$ |
| MINKEY | $$O(1)$$ |
| УМЕНЬШЕНИЕ_КЛЮЧА $$(i, D)$$ | $$O(\log_d n)$$ |
| ОБРАЗОВАTЬ_ОЧЕРЕДЬ | $$O(n)$$ |
| СПИСОК_МИН $$(x, h)$$ | $$O(d k)$$ |
Замечание. Для $$d$$ -куч "неудобной" является операция слияния куч.
Под задачей сортировки в простейшем случае понимают следующее: дана последовательность $$({\rm key}[1],\,{\rm key}[2],\, \ldots,\, {\rm key}[{n}])$$ из $$n$$ элементов некоторого линейно упорядоченного множества, например целых или вещественных чисел, записанных в массив $${\rm key}$$. Требуется переставить элементы массива так, чтобы после перестановки выполнялись неравенства:$$\eq*{ {\rm key}[1] \le {\rm key}[2] \le \ldots \le {\rm key} [n]. }$$
Уточнения этой задачи связаны с теми средствами, с помощью которых предполагается ее решение. Нас интересуют алгоритмы с точки зрения их компьютерной реализации. Оценивая качество различных алгоритмов, обычно интересуются тем, как зависит время счета от длины $$n$$ сортируемой последовательности и требуется ли для этого дополнительная память, размер которой определяется параметром $$n$$. Существенную роль при этом играет метод доступа к элементам памяти. При сортировке во внутренней (оперативной) памяти обычно используется прямой доступ, а во внешней — последовательный.
Бесхитростный алгоритм сортировки может заключаться в выполнении следующих операторов:
$$\formula{ \t for\ {k}:= 1\ \t to\ n - 1\ \t do for\ i:= k+ 1\ \t to\ n\ \t do\ \t if\ {\rm key}[{i}] < {\rm key}[{k}]\ \t then\ {\rm tr}({i},{k}); }$$
Здесь $${\rm tr}({i},{k})$$ — процедура, транспонирующая элементы $${\rm key}[{i}],\, {\rm key}[{k}]$$. Заметим, что число сравнений$$\eq*{ "{\rm key}[{i}] < {\rm key}[{k}]" }$$ при реализации такого алгоритма равно $$n(n - 1)/2$$. В частности, это означает, что время работы алгоритма равно $$O(n^2)$$.
Предположим, что в нашем распоряжении имеется процедура РАЗДЕЛЯЙ $$(i, j, k)$$, которая по заданным значениям индексов $$i$$, $$j$$ находит некоторое промежуточное значение $$k$$ и переставляет элементы сегмента $${\rm key}[i \ldots j]$$ так, чтобы для $$s = {i},\,{i} + 1,\,\ldots,\,{k} - 1$$ выполнялось неравенство $${\rm key}[{s}] \le {\rm key}[k]$$, а для $$s = k + 1,\, k + 2,\, \ldots, j$$ — неравенство $${\rm key}[{k}] \le {\rm key}[{s}]$$.
Тогда для сортировки сегмента $${\rm key}[{i} \ldots {j}]$$ может быть использована рекурсивная процедура СОРТИРУЙ.
$$\formula{ \t{procedure СОРТИРУЙ}\ (i, j);\\ \t begin\ \t if\ {i} = {j}\ \t then\ \t{exit}\ \t else\\ \mbox{}\q \t{РАЗДЕЛЯЙ}\ ({i}, {j}, {k});\ \t{СОРТИРУЙ}\ (i, k - 1);\ \t{СОРТИРУЙ}\ (k + 1, j)\}\\ \t end; }$$
Для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ $$(1, n)$$.
Заметим, что если бы процедура РАЗДЕЛЯЙ работала линейное от длины сегмента время и давала значение $$k$$, близкое к середине между $$i$$ и $$j$$, то число обращений к ней приблизительно равнялось бы $$\log n$$ и сортировка всего массива проходила бы за время порядка $$O(n \cdot \log n)$$. Однако можно доказать, что при естественной реализации эта оценка справедлива лишь в среднем.
Упражнения
Этот метод является разновидностью метода "разделяй и властвуй"; впрочем, уместнее было бы назвать его "властвуй и объединяй".
Предположим, что у нас есть процедура СЛИВАЙ ( $$i, j, k)$$, которая два уже отсортированных сегмента $${\rm key}[{i}\ldots (j - 1)]$$ и $${\rm key}[{j}\ldots {k}]$$ преобразует (сливает) в один сегмент $${\rm key}[{i}\ldots {k}]$$, делая его полностью отсортированным. Тогда рекурсивная процедура
$$\formula{ \t{procedure СОРТИРУЙ}\ (i, j);\\ \t begin\ \t{if}\ {i} = {j}\ \t then\ \t{exit}\ \t else\\ \mbox{}\q \{m:= (i + j)\ \t div\ 2;\ \t{СОРТИРУЙ}\ (i, m);\ \t{СОРТИРУЙ}\ (m+1, j);\\ \mbox{}\q \t{СЛИВАЙ} (i, m, j)\}\\ \t end; }$$
очевидно, сортирует сегмент $${\rm key}[{i}\ldots {j}]$$, а для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ $$(1, n)$$. Как видим, вопрос балансировки размера сегментов решается здесь просто. Число обращений к процедуре СЛИВАЙ $$(i, m, j)$$ равно $$\log n$$, а время ее выполнения легко сделать линейным от суммарной длины сливаемых сегментов.
Упражнения
Для представления сортируемой последовательности используем структуру $$d$$-кучи. Сортировку можно провести в два этапа. Данный алгоритм (heapsort) работает для бинарных деревьев (d=2) и это необходимо указывать
Эти два этапа реализуются с помощью процедуры SORT, которая сортирует массив по убыванию ключей:
$$\formula{ \t{procedure SORT}(n);\\ \t begin\ \t{for}\ i:= n - 1\ \t downto\ 0\ \t do\ \t{ПОГРУЖЕНИЕ}\ (i);\\ \mbox{}\q \t while\ n > 1\ \t do\ \{{\rm tr} (1, n);\ n:= n - 1;\ \t{ПОГРУЖЕНИЕ} (1)\}\\ \t end; }$$
Заметим, что процедура $$SORT$$ не требует дополнительной памяти, размер которой зависел бы от длины массива $$\rm key$$.
Упражнения
в процедуре $$SORT$$ можно заменить оператором
$$\eq*{ \t for\ i := n \t div\ 2\ \t downto\ 0\ \t do\ \t{ПОГРУЖЕНИЕ}\ (i).$$Приводимый ниже алгоритм Дейкстры корректно решает задачу для графов с неотрицательными весами вершин. Если же в графе есть ребра с отрицательными весами, но нет циклов с отрицательным суммарным весом, то для решения задачи можно использовать алгоритм Форда, Беллмана.
Упражнение
Напишите на каком-либо алгоритмическом языке реализацию алгоритма Дейкстры с использованием $$d$$ -кучи и испытайте ее на тестовых примерах при различных значениях $$d$$.
Приоритетная очередь — это абстрактный тип данных, предназначенный для представления взвешенных множеств. Множество называется взвешенным, если каждому его элементу однозначно соответствует число, называемое ключом или весом. Основными операциями над приоритетной очередью являются следующие операции:
Дополнительные операции над приоритетными очередями:
Приоритетная очередь естественным образом используется в таких задачах, как сортировка элементов массива, поиск во взвешенном неориентированном графе минимального остовного дерева, поиск кратчайших путей от заданной вершины взвешенного графа до его остальных вершин, и во многих других.
Приоритетную очередь можно представить с помощью массива или списка элементов, но такие реализации неэффективны по времени выполнения основных операций. Так, например, поиск элемента с минимальным ключом в неупорядоченном массиве или списке требует последовательного просмотра всех его элементов. Если поддерживать упорядоченность массива или списка по ключу, то "неудобной" окажется операция вставки нового элемента.
Чаще всего приоритетная очередь представляется с помощью
Соответствие между узлами дерева и элементами множества называется кучеобразным, если для каждого узла $$i$$ соблюдается следующее условие:
Ключ элемента, приписанного узлу $$i$$, не превосходит ключей, приписанных его потомкам.
Такие представления взвешенных множеств называются
Представление приоритетной очереди с помощью $$d$$ -кучи основано на использовании так называемых завершенных $$d$$ -арных деревьев ( $${d \ge 2}$$ ).
Завершенное $$d$$ -арное дерево — это корневое дерево со следующими свойствами:
Узлы завершенного $$d$$ -арного дерева принято нумеровать следующим образом: корень получает номер 0, потомки узла с номером $$i$$ получают номера: $$i\cdot d + 1$$, $$i\cdot d + 2$$, $$\ldots$$, $$i\cdot d + d$$. Такая нумерация удобна тем, что позволяет разместить узлы дерева в массиве в порядке возрастания их номеров, при этом позиции потомков любого узла в массиве легко вычисляются по позиции самого узла. Так же легко по позиции узла вычислить позицию его родителя. Так, для узла, расположенного в позиции $$i$$, родительский узел располагается в позиции $$(i - 1) \mathop{\rm div} d$$, где $$\mathop{\rm div}$$ — операция деления нацело.
В изображении завершенного $$d$$ -арного дерева узлы одинаковой глубины удобно располагать на одном уровне, при этом потомки одного узла располагаются слева направо в порядке объявленных номеров. При таком рисовании нижний уровень заполняется, возможно, не полностью.
Отметим некоторые простые утверждения о завершенных $$d$$ -арных деревьях, которые будут полезны при анализе трудоемкости основных операций.
Утверждение 1. Длина $$h$$ пути из корня завершенного $$d$$ -арного дерева с $$n > 1$$ узлами в любой лист удовлетворяет неравенствам:$$\eq*{ \log_d n - 1 < h < \log_d n + 1. }$$
Доказательство Минимальное количество узлов в $$d$$ -куче высоты $$h$$ ( $$h > 0$$ ), по свойствам 2 и 3 $$d$$ -арного дерева, очевидно, равно $$1 + d + d^2 + \ldots + d^{h - 1} + 1$$ (последний уровень содержит лишь один узел).
Максимальное количество узлов в такой $$d$$ -куче равно $$1 + d + d^2 + \ldots + d^h$$ (последний уровень содержит $$d^h$$ узлов). Отсюда имеем неравенства:$$\eq*{ (1 + d + d^2 + \ldots + d^h - 1 + 1) \le n \le (1 + d + d^2 + \ldots + d^h). }$$
Суммируя левую и правую части как геометрические прогрессии, получим$$\eq*{ (d^h - 1)/(d - 1) + 1 \le n \le (d^{h + 1} - 1)/(d - 1), }$$ и после некоторых очевидных оценок с помощью логарифмирования получаем требуемые неравенства:$$\eq*{ \log_d n - 1 < h < \log_d n + 1. }$$
Утверждение 2. Количество узлов высоты $$h$$ не превосходит $$n/d^h$$.
Под высотой узла понимается расстояние от него до наиболее далекого потомка. Кучу, содержащую $$n$$ элементов, будем представлять двумя массивами — $$a[0 \ldots n - 1]$$ и $${\rm key}[0 \ldots n - 1]$$, — полагая что $$a[i]$$ — имя элемента, приписанного узлу $$i$$ ; $${\rm key}[i]$$ — его ключ. Иногда под $$a[i]$$ удобно понимать сам элемент исходного множества или ссылку на него. В некоторых прикладных задачах нет необходимости помещать в приоритетную очередь ни сами элементы, ни их имена, в таких случаях при организации кучи используется лишь массив $${\rm key}[0 \ldots n - 1]$$.
На рис. 4.1 приведен пример кучи для $$d = 3$$, $$n = 18$$. Кружочками изображены узлы дерева, в них записаны элементы массива, представляющие имена элементов кучи.
Пример кучи при $$d = 3$$, $$n = 7$$ для приоритетной очереди, содержащей элементы с ключами $$1, 2, 2, 2, 3, 4, 5$$, изображен на рис. 4.2, где пара чисел в каждом кружочке обозначает номер узла и ключ соответствующего элемента.
(рис 4.2) (рис 4.1) При реализации основных операций над кучами используются две вспомогательные операции — ВСПЛЫТИЕ и ПОГРУЖЕНИЕ. При реализации этих операций введем еще одну вспомогательную операцию — транспонирование, с помощью которой будем менять местами элементы, расположенные в двух разных узлах дерева. Ее реализация может быть представлена следующим образом:
$$\formula{ \t{procedure}\ tr(i, j);\\ \t begin\\ \mbox{}\q {\rm temp}0:= a[i]; a[i]:= a[j];\ a[j]:= {\rm temp}0; \\ \mbox{}\q {\rm temp}1:= {\rm key}[i];\ {\rm key}[i]:= {\rm key}[j];\ {\rm key}[j]:= {\rm temp}1;\\ \t end; }$$Замечание. Если в кучу помещаются только ключи элементов, то процедура транспонирования модифицируется соответствующим образом.
Операция ВСПЛЫТИЕ.Эта операция применяется в тех случаях, когда в некотором узле, например в $$i$$ -м, расположен элемент $$x$$, нарушающий кучеобразный порядок так, что его ключ меньше ключа его родителя $$y$$.
Элементы $$x$$ и $$y$$ меняются местами. Если после этого элемент $$x$$ снова не удовлетворяет условиям кучи, то еще раз проводится аналогичная перестановка. И так до тех пор, пока $$x$$ не встанет на свое место.
Рассмотрим 3-дерево на рис. 4.3. В этом дереве кучеобразный порядок нарушает узел $$17$$ с ключом $$14$$, так как его родительскому узлу приписан элемент с ключом $$31 > 14$$.
(рис 4.3) Применим к узлу $$17$$ операцию ВСПЛЫТИЕ. Элементы с ключами $$31$$ и $$14$$ меняются местами. В результате получается дерево, представленное на рис. 4.4.
(рис 4.4) Теперь нарушен кучеобразный порядок в узле $$5$$ ( $$21 > 14$$ ), меняем местами элементы c ключами $$21$$ и $$14$$. В результате получаем кучу, изображенную на рис. 4.5. Кучеобразный порядок восстановлен, операция ВСПЛЫТИЕ завершена.
(рис 4.5) Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Это число, очевидно, не более чем удвоенное число узлов в пути от узла $$x$$ до корня дерева. Длина такого пути в $$d$$ -куче с $$n$$ узлами не превосходит ее высоты, а именно $$\log_d n + 1$$, в соответствии с доказанным выше утверждением 1. Значит, время выполнения данной операции — $$O(\log_d n)$$.
Реализация операции ВСПЛЫТИЕ. Входным параметром этой операции является номер узла, в котором нарушен порядок:
$$\formula{ \t{procedure ВСПЛЫТИЕ}(i);\\ \t{begin}\\ p:= (i - 1)\ \t div\ d;\\ \mbox{}\q\t while (i \ne 0)\ \t and\ ({\rm key}[p] > {\rm key}[i])\ \t do\ \{{\rm tr}(i, p);\ i:= p;\ p:= (i - 1)\ \t div\ d\};\\ \t end; }$$Замечание.
Операция ПОГРУЖЕНИЕ. Эта операция также применяется для восстановления свойства кучеобразности. Пусть, например, в $$i$$ -м узле расположен элемент $$x$$, нарушающий кучеобразный порядок таким образом, что ключ элемента $$x$$ больше ключа элемента $$y$$, приписанного потомку узла $$i$$. В этом случае среди непосредственных потомков узла $$i$$ выбирается элемент $$y$$ с наименьшим ключом, и элементы $$x$$ и $$y$$ меняются местами. Если после этого элемент $$x$$ снова не удовлетворяет условиям кучи, то еще раз проводим аналогичную перестановку. И так до тех пор, пока $$x$$ не встанет на свое место.
Рассмотрим $$3$$ -дерево, представленное на рис. 4.6. В узле $$1$$ расположен элемент $$x$$ с ключом $$31$$, и этот узел имеет двух потомков с меньшими ключами, а именно $$30$$ и $$14$$. Применим к элементу $$x$$ операцию ПОГРУЖЕНИЕ.
(рис 4.6) Среди непосредственных потомков узла 1 находим узел, которому приписан элемент $$y$$ с наименьшим ключом, в нашем случае это узел $$5$$ c ключом $$14$$. Меняем местами элементы $$x$$ и $$y$$. В результате получается дерево, изображенное на рис. 4.7.
(рис 4.7) Теперь элемент $$x$$ снова имеет потомка с меньшим, чем у него, ключом (а точнее, оба его потомка имеют меньшие ключи). Снова находим непосредственного потомка элемента $$x$$ с наименьшим ключом, и меняем его и $$x$$ местами. Получается дерево, изображенное на рис. 4.8.
(рис 4.8) Теперь $$x$$ находится в узле 17 и не имеет потомков с меньшим, чем у него, ключом (точнее, у него вообще нет потомков). Операция ПОГРУЖЕНИЕ завершена.
Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Для каждого узла в пути следования данной операции производится $$d$$ сравнений (при поиске потомка с минимальным ключом) и один обмен. Длина этого пути в $$d$$ -куче с $$n$$ узлами не превосходит ее высоты, а именно $$\log_d n$$, по доказанному выше утверждению 1. Значит, время выполнения данной операции — $$O(d\cdot \log_d n)$$.
Для реализации операции погружения воспользуемся функцией $${\rm minchild} (i)$$, позволяющей для любого узла $$i$$ находить его непосредственного потомка с минимальным ключом. Если у узла $$i$$ нет потомков, то $${\rm minchild} (i) = 0$$.
Реализация операции ПОГРУЖЕНИЕ
$$\formula{ \t{procedure ПОГРУЖЕНИЕ}(i);\\ \t begin \\ \mbox{}\q c:= {\rm minchild}(i);\\ \mbox{}\q \t while\ (c \ne 0)\ \t and\ ({\rm key}[c] < {\rm key}[i])\ \t do\ \{{\rm tr}(i, c);\ i:= c;\ c := {\rm minchild} (c)\}\\ \t end; }$$ $$\formula{ \t function\ {\rm minchild} (i);\\ \t begin\ \t if\ i\cdot d + 1 > n\ \t then\ {\rm minchild} := 0\ \t else\\ \mbox{}\q \t begin\\ \mbox{}\q\qq {\rm first\_child}:= i\cdot d + 1;\ {\rm last\_child}:= \min((i + 1)\cdot d - 1, n);\\ \mbox{}\q\qq{\rm min\_key} := {\rm key}[{\rm first\_child}];\\ \mbox{}\q\qq \t for\ i := {\rm first\_child}\ \t to\ {\rm last\_child}\ \t do\ \t if\ {\rm key}[i] > {\rm min\_key}\ \t then\\ \mbox{}\q\qq\qq \{{\rm min\_key} := {\rm key}[i];\ {\rm minchild} := i\}\\ \mbox{}\q \t end\\ \t end }$$Операция ВСТАВКА. Если перед выполнением этой операции куча содержала $$n$$ узлов (напомним, что они пронумерованы числами от $$0$$ до $${n - 1}$$ ), то добавляем к дереву $$(n + 1)$$ -й узел (его номер будет $$n$$ ) и приписываем ему элемент с именем $${\rm name}X$$ и ключом $${\rm key}X$$. Вставка нового элемента производится посредством отведения для него места в $$n$$ -ых позициях массивов $$a$$ и $${\rm key}$$ соответственно, после чего к добавленному узлу применяется операция ВСПЛЫТИЕ для восстановления кучеобразного порядка.
Вставим в $$d$$ -кучу, изображенную на рис. 4.9, новый элемент с ключом $$14$$.
(рис 4.9) Сначала добавляем к дереву новый узел с номером $$17$$ и приписываем ему элемент с ключом $$14$$. Получим дерево, представленное на рис. 4.10.
(рис 4.10) Затем применяем к узлу $$17$$ операцию ВСПЛЫТИЕ. При описании этой операции использовался именно приведенный пример (см. рис. 4.3, 4.4, 4.5).
Вычислительная сложность данной операции равна константе плюс вычислительная сложность операции ВСПЛЫТИЕ, то есть $$O(\log_d n)$$.
Реализация операции ВСТАВКА
$$\formula{ \t{procedure ВСТАВКА}\ ({\rm name}X, {\rm key}X);\\ \t begin\ {a}[{n}]:= {\rm name}X; {\rm key}[{n}]:= {\rm key}X;\ \t{ВСПЛЫТИЕ}\ ({n});\ {n}:= {n} + 1\ \t end; }$$Операция УДАЛЕНИЕ. Используется для удаления элемента, приписанного узлу с заданным номером $$i$$. Сначала элемент, приписанный последнему узлу дерева, переносится на место удаляемого элемента, последний узел при этом становится ненужным и поэтому удаляется из дерева. Далее, если узел $$i$$, в который помещен новый элемент, имеет родителя с большим ключом, то к узлу $$i$$ применяется операция ВСПЛЫТИЕ, в противном случае — ПОГРУЖЕНИЕ.
Таким образом, ориентируясь на худший случай, вычислительную сложность операции УДАЛЕНИЕ оцениваем величиной $$O(d\cdot \log_d n)$$.
Реализация операции УДАЛЕНИЕ
$$\formula{ \t{procedure УДАЛЕНИЕ}(i);\\ \t begin\ {a}[{i}]:= {a}[{n} - 1];\ {\rm key}[{i}]:= {\rm key}[{n} - 1];\ {n}:= {n} - 1; \\ \mbox{}\q \t if\ i \ne 0\ \t and\ {\rm key}[{i}] ({\rm key}[(i - 1) \mathop{\rm div} {d}]\ \t then\ \t{ВСПЛЫТИЕ}({i})\\ \mbox{}\q \t else\ \t{ПОГРУЖЕНИЕ}({i})\\ \t end; }$$Операция УДАЛЕНИЕ_МИНИМУМА. Эта операция предназначена для взятия из кучи элемента с минимальным ключом (он находится в корне дерева) и удаления его из кучи с помощью операции УДАЛЕНИЕ.
Реализация операции УДАЛЕНИЕ_МИНИМУМА
$$\formula{ \t{procedure УДАЛЕНИЕ\_МИНИМУМА}\ ({\rm name}X, {\rm key}X);\\ \t begin\ {\rm name}X:= {a}[0];\ {\rm key}X:= {\rm key}[0];\ \t{УДАЛЕНИЕ}\ (0)\ \t end; }$$Функция MINKEY. Эта функция предназначена для определения минимального ключа без удаления соответствующего элемента.
Реализация функции MINKEY
$$\formula{ \t function\ {\rm MINKEY};\ \t begin\ {\rm MINKEY}: = {\rm key}[0]\ \t end; }$$Трудоемкость операции, очевидно, равна $${O}(1)$$.
Операция УМЕНЬШЕНИЕ_КЛЮЧА. Предназначена для
Вычислительная сложность данной операции определяется временем,
затрачиваемым на
Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА
$$\formula{ \t{procedure УМЕНЬШИТЬ\_КЛЮЧ}\ (i, delta);\\ \t begin\ {\rm key}[{i}] := {\rm key}[{i}] - {delta};\ \t{ВСПЛЫТИЕ}\ (i);\ \t end; }$$
Операция ОКУЧИВАНИЕ. Заметим, что если $$d$$ -куча создается путем $$n$$ -кратного применения операции ВСТАВКА, то суммарная трудоемкость ее создания будет равна $$O(n\cdot \log_d n)$$. Если же все $$n$$ элементов сначала занимают в произвольном порядке массив $$a[0 \ldots (n - 1)]$$ и, соответственно, массив $${\rm key}[0 \ldots ({n} - 1)]$$, то можно превратить их в $$d$$ -кучу, применяя операцию ПОГРУЖЕНИЕ по очереди к узлам $$(n - 1),\,(n - 2),\,\ldots,\,0$$.
Такой процесс будем называть окучиванием массива. Для доказательства того, что в результате действительно устанавливается кучеобразный порядок, достаточно заметить, что если поддеревья с корнями в узлах $$n - 1,\, n - 2,\, \ldots,\, i + 1$$ упорядочены по правилу кучи, то после применения процедуры ПОГРУЖЕНИЕ к узлу $$i$$ поддерево с корнем в этом узле также станет упорядоченным по правилу кучи. Итак, остановимся на следующей реализации.
Реализация операции ОКУЧИВАНИЕ
$$\formula{ \t{procedure ОКУЧИВАНИЕ};\\ \t begin\\ \mbox{}\q \t for\ i:= n - 1\ \t downto\ 0\ \t do\ \t{ПОГРУЖЕНИЕ}\ (i)\\ \t end; }$$Утверждение 3. Вычислительная сложность операции ОКУЧИВАНИЕ равна $$O(n)$$.
Доказательство Заметим, что трудоемкость погружения с высоты $$h$$ равна $$O(h)$$, а количество узлов высоты $$h$$ не превосходит $$n/d^h$$. Осталось оценить сумму$$\eq*{ \suml_{h=1}^{H} h\frac{n}{d^{h}}, }$$ где $$H = \lceil \log_d n\rceil$$, и убедиться, что полученная сумма есть $$O(n)$$.
Для суммирования можно воспользоваться формулой$$\eq*{ \suml_{i=1}^k \frac{i}{x^i} = \frac{x^{k+1} - (k-1) x + k}{x^k (x-1)^2}. }$$
Предоставляем читателю возможность завершить доказательство.
Операция СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ. Эта операция применяется для получения списка элементов, которые имеют ключи, меньшие заданного значения $${\rm key}0$$, и реализуется следующим образом. Если ключ элемента, находящегося в корне, больше, чем $${\rm key}0$$, то это дерево не имеет искомых элементов. В противном случае включаем его в выходной список $$S$$, а затем применяем ту же процедуру ко всем потомкам узла, включенного в список.
Пусть куча содержит $$k$$ элементов с ключами, меньшими, чем $${\rm key}0$$. По свойству кучи, они все расположены на ее "верхушке". Данная процедура обходит эту верхушку за время, пропорциональное $$k$$, и для каждого из этих $$k$$ элементов просматривает все его $$d$$ (или меньше) непосредственных потомков. Получаем, что время выполнения данной процедуры является величиной $$O(d\cdot k)$$.
Реализация операции СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ
$$\formula{ \t{procedure СОЗДАТЬ\_СПИСОК\_МИНИМАЛЬНЫХ}(S, {\rm key}0);\\ \t begin\\ \mbox{}\q \t{Инициализируем пустой список} S; \\ \mbox{}\q \t{Инициализируем стек};\\ \mbox{}\q 0 \Rightarrow \t{стек};\\ \mbox{}\q \t{ while стек не пуст do}\\ \mbox{}\q\qq \t{begin стек} \Rightarrow i;\\ \mbox{}\q\qq\qq if ({\rm key}[i] < {\rm key}0)\ \t{then Добавить} a[i]\ \t{к списку}\ S;\\ \mbox{}\q\qq\qq \t for\ j:=d^\ast i + 1\ \t to\ d^\ast(i + 1)\ \t do if\ j \le (n - 1)\ \t then\ j \Rightarrow \t{стек};\\ \mbox{}\q\qq \t end\\ \t end }$$
Сводные данные о трудоемкости операций с d-кучами
| ВСПЛЫТИЕ $$(i)$$ | $$O(\log_d n)$$ |
| ПОГРУЖЕНИЕ $$(i)$$ | $$O(d \log_d n)$$ |
| ВСТАВКА $$({\rm name}X, {\rm key}X)$$ | $$O(\log_d n)$$ |
| УДАЛЕНИЕ $$(i)$$ | $$O(d \log_d n)$$ |
| УДАЛЕНИЕ_МИН $$({\rm name}X, {\rm key}X)$$ | $$O(d \log_d n)$$ |
| MINKEY | $$O(1)$$ |
| УМЕНЬШЕНИЕ_КЛЮЧА $$(i, D)$$ | $$O(\log_d n)$$ |
| ОБРАЗОВАTЬ_ОЧЕРЕДЬ | $$O(n)$$ |
| СПИСОК_МИН $$(x, h)$$ | $$O(d k)$$ |
Замечание. Для $$d$$ -куч "неудобной" является операция слияния куч.
Под задачей сортировки в простейшем случае понимают следующее: дана последовательность $$({\rm key}[1],\,{\rm key}[2],\, \ldots,\, {\rm key}[{n}])$$ из $$n$$ элементов некоторого линейно упорядоченного множества, например целых или вещественных чисел, записанных в массив $${\rm key}$$. Требуется переставить элементы массива так, чтобы после перестановки выполнялись неравенства:$$\eq*{ {\rm key}[1] \le {\rm key}[2] \le \ldots \le {\rm key} [n]. }$$
Уточнения этой задачи связаны с теми средствами, с помощью которых предполагается ее решение. Нас интересуют алгоритмы с точки зрения их компьютерной реализации. Оценивая качество различных алгоритмов, обычно интересуются тем, как зависит время счета от длины $$n$$ сортируемой последовательности и требуется ли для этого дополнительная память, размер которой определяется параметром $$n$$. Существенную роль при этом играет метод доступа к элементам памяти. При сортировке во внутренней (оперативной) памяти обычно используется прямой доступ, а во внешней — последовательный.
Бесхитростный алгоритм сортировки может заключаться в выполнении следующих операторов:
$$\formula{ \t for\ {k}:= 1\ \t to\ n - 1\ \t do for\ i:= k+ 1\ \t to\ n\ \t do\ \t if\ {\rm key}[{i}] < {\rm key}[{k}]\ \t then\ {\rm tr}({i},{k}); }$$
Здесь $${\rm tr}({i},{k})$$ — процедура, транспонирующая элементы $${\rm key}[{i}],\, {\rm key}[{k}]$$. Заметим, что число сравнений$$\eq*{ "{\rm key}[{i}] < {\rm key}[{k}]" }$$ при реализации такого алгоритма равно $$n(n - 1)/2$$. В частности, это означает, что время работы алгоритма равно $$O(n^2)$$.
Предположим, что в нашем распоряжении имеется процедура РАЗДЕЛЯЙ $$(i, j, k)$$, которая по заданным значениям индексов $$i$$, $$j$$ находит некоторое промежуточное значение $$k$$ и переставляет элементы сегмента $${\rm key}[i \ldots j]$$ так, чтобы для $$s = {i},\,{i} + 1,\,\ldots,\,{k} - 1$$ выполнялось неравенство $${\rm key}[{s}] \le {\rm key}[k]$$, а для $$s = k + 1,\, k + 2,\, \ldots, j$$ — неравенство $${\rm key}[{k}] \le {\rm key}[{s}]$$.
Тогда для сортировки сегмента $${\rm key}[{i} \ldots {j}]$$ может быть использована рекурсивная процедура СОРТИРУЙ.
$$\formula{ \t{procedure СОРТИРУЙ}\ (i, j);\\ \t begin\ \t if\ {i} = {j}\ \t then\ \t{exit}\ \t else\\ \mbox{}\q \t{РАЗДЕЛЯЙ}\ ({i}, {j}, {k});\ \t{СОРТИРУЙ}\ (i, k - 1);\ \t{СОРТИРУЙ}\ (k + 1, j)\}\\ \t end; }$$
Для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ $$(1, n)$$.
Заметим, что если бы процедура РАЗДЕЛЯЙ работала линейное от длины сегмента время и давала значение $$k$$, близкое к середине между $$i$$ и $$j$$, то число обращений к ней приблизительно равнялось бы $$\log n$$ и сортировка всего массива проходила бы за время порядка $$O(n \cdot \log n)$$. Однако можно доказать, что при естественной реализации эта оценка справедлива лишь в среднем.
Упражнения
Этот метод является разновидностью метода "разделяй и властвуй"; впрочем, уместнее было бы назвать его "властвуй и объединяй".
Предположим, что у нас есть процедура СЛИВАЙ ( $$i, j, k)$$, которая два уже отсортированных сегмента $${\rm key}[{i}\ldots (j - 1)]$$ и $${\rm key}[{j}\ldots {k}]$$ преобразует (сливает) в один сегмент $${\rm key}[{i}\ldots {k}]$$, делая его полностью отсортированным. Тогда рекурсивная процедура
$$\formula{ \t{procedure СОРТИРУЙ}\ (i, j);\\ \t begin\ \t{if}\ {i} = {j}\ \t then\ \t{exit}\ \t else\\ \mbox{}\q \{m:= (i + j)\ \t div\ 2;\ \t{СОРТИРУЙ}\ (i, m);\ \t{СОРТИРУЙ}\ (m+1, j);\\ \mbox{}\q \t{СЛИВАЙ} (i, m, j)\}\\ \t end; }$$
очевидно, сортирует сегмент $${\rm key}[{i}\ldots {j}]$$, а для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ $$(1, n)$$. Как видим, вопрос балансировки размера сегментов решается здесь просто. Число обращений к процедуре СЛИВАЙ $$(i, m, j)$$ равно $$\log n$$, а время ее выполнения легко сделать линейным от суммарной длины сливаемых сегментов.
Упражнения
Для представления сортируемой последовательности используем структуру $$d$$-кучи. Сортировку можно провести в два этапа. Данный алгоритм (heapsort) работает для бинарных деревьев (d=2) и это необходимо указывать
Эти два этапа реализуются с помощью процедуры SORT, которая сортирует массив по убыванию ключей:
$$\formula{ \t{procedure SORT}(n);\\ \t begin\ \t{for}\ i:= n - 1\ \t downto\ 0\ \t do\ \t{ПОГРУЖЕНИЕ}\ (i);\\ \mbox{}\q \t while\ n > 1\ \t do\ \{{\rm tr} (1, n);\ n:= n - 1;\ \t{ПОГРУЖЕНИЕ} (1)\}\\ \t end; }$$
Заметим, что процедура $$SORT$$ не требует дополнительной памяти, размер которой зависел бы от длины массива $$\rm key$$.
Упражнения
в процедуре $$SORT$$ можно заменить оператором
$$\eq*{ \t for\ i := n \t div\ 2\ \t downto\ 0\ \t do\ \t{ПОГРУЖЕНИЕ}\ (i).$$Приводимый ниже алгоритм Дейкстры корректно решает задачу для графов с неотрицательными весами вершин. Если же в графе есть ребра с отрицательными весами, но нет циклов с отрицательным суммарным весом, то для решения задачи можно использовать алгоритм Форда, Беллмана.
Упражнение
Напишите на каком-либо алгоритмическом языке реализацию алгоритма Дейкстры с использованием $$d$$ -кучи и испытайте ее на тестовых примерах при различных значениях $$d$$.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.