Амортизационный анализ
Наряду с получением верхних и нижних оценок и оценок в среднем, часто используются так называемые амортизационные оценки.
Амортизационный анализ применяется при оценке времени выполнения корректной последовательности, состоящей из однотипных или разнотипных операций с некоторой структурой данных. Если верхнюю оценку времени выполнения одной операции умножить на , получим верхнюю оценку выполнения всех операций. Часто такая оценка бывает сильно завышенной. Иногда длительное время выполнения очередной операции влечет за собой малое время выполнения следующих операций. Более того, такая ситуация может создаваться искусственно, то есть при выполнении очередной операции мы можем готовить почву для более эффективного выполнения следующей. Поэтому возникает задача изучения асимптотического поведения гарантированной оценки для среднего времени выполнения одной операции.
При амортизационном анализе определяется некоторая так называемая учетная (амортизационная) стоимость одной операции, которая может быть как больше, так и меньше реальной стоимости конкретной операции. Но при этом для любой корректной последовательности операций фактическая суммарная длительность всех операций не должна превосходить суммы их учетных стоимостей. Зная учетную стоимость одной операции, верхнюю оценку времени выполнения последовательности из операций можно получить, умножив ее на .
Ниже рассмотрим три часто используемых метода амортизационного анализа: метод группировки, метод предоплаты и метод потенциалов.
Метод группировки. Предположим, что мы оценили сверху время выполнения последовательности из операций, установив, что она не превосходит , тогда величину
объявим учетной стоимостью любой операции из рассматриваемой последовательности, независимо от ее длительности.
Метод предоплаты. В этом методе операции разных типов получают разные учетные стоимости, причем эти стоимости могут быть как больше, так и меньше фактических. Если учетная стоимость превосходит фактическую, то разность между ними рассматривается как резерв на оплату в будущем тех операций, у которых учетная стоимость ниже реальной.
Учетные стоимости должны выбираться так, чтобы в любой момент времени фактическая стоимость не превосходила суммы учетных стоимостей, то есть чтобы резерв оставался неотрицательным.
Метод потенциалов. Этот метод является обобщением метода предоплаты. Здесь резерв определяется функцией состояния структуры данных в целом. Эта функция называется потенциалом.
Общая схема метода такова. Пусть над структурой данных предстоит произвести операций, и пусть — состояние структуры данных после -й операции ( — исходное состояние). Потенциал представляет собой функцию
из множества возможных состояний структуры данных в множество действительных чисел.
Пусть — реальная стоимость -й операции. Учетной стоимостью -й операции объявим число , определяемое формулой
как сумма реальной стоимости операции плюс приращение потенциала в результате выполнения этой операции. Тогда суммарная учетная стоимость всех операций равна
Если нам удалось придумать функцию , для которой
то суммарная учетная стоимость даст верхнюю оценку для реальной стоимости последовательности из операций. Не ограничивая общности, можно считать, что
Говоря неформально, если разность потенциалов
положительна, то учетная стоимость -й операции включает в себя резерв (предоплату за будущие операции); если же эта разность отрицательна, то учетная стоимость -й операции меньше реальной и разница покрывается за счет накопленного к этому моменту потенциала.
Учетные стоимости и оценки реальной стоимости, рассчитанные с помощью метода потенциалов, зависят от выбора потенциальной функции, а сам этот выбор является делом творческим.
Ниже эти три метода будут проиллюстрированы на примере анализа работы двоичного счетчика с единственной операцией Increment (прибавление единицы).
Амортизационный анализ работы двоичного счетчика
Рассмотрим работу -разрядного двоичного сбрасываемого счетчика, реализованного как массив битов , хранящий двоичную запись числа . Будем считать, что — младший разряд. Пусть первоначально . Единственной операцией в нашем примере будет операция Increment, увеличивающая на 1 по модулю .
Увеличение счетчика на единицу происходит следующим образом: все начальные единичные биты в массиве , если они есть, становятся нулями, а следующий непосредственно за ними нулевой бит, если он есть, устанавливается в единицу. Стоимость операции Increment линейно зависит от общего количества битов, подвергшихся изменению. Каждое такое изменение будем считать элементарной операцией.
Анализ работы двоичного счетчика методом группировки. Применим метод группировки для анализа сложности -кратного выполнения операции Increment. Поскольку в худшем случае, когда массив состоит из одних единиц, меняются все
битов, то -кратное выполнение операции Increment может быть оценено как элементарных операций. Но эта оценка слишком груба.
Чтобы получить более точную оценку, учтем, что не каждый раз значения всех битов меняются. В самом деле, младший бит меняется при каждом исполнении операции Increment. Следующий по старшинству бит меняется только через раз. При счете от нуля до этот бит меняется раз. Бит меняется только каждый четвертый раз, и так далее. Заметим, что если , то в процессе счета от до
разряд меняется раз, а если , то он вообще не меняется. Следовательно, общее количество операций зануления и записи 1 равно
Тем самым, увеличение двоичного счетчика от до
требует не более операций, причем константа не зависит от и равна . Учетную стоимость операции Increment можно считать равной .
Анализ работы двоичного счетчика методом предоплаты. Применим метод предоплаты для анализа сложности -кратного выполнения операции Increment. Будем считать, что реальная стоимость изменения бита составляет рубль. Установим такие учетные стоимости: рубля за запись единицы, за очистку. При каждой установке бита в единицу одним из двух рублей учетной стоимости будем расплачиваться за реальные затраты на эту установку, а второй рубль, остающийся в резерве, будем "прикреплять" к рассматриваемому биту.
Поскольку первоначально все биты были нулевыми, в каждый момент к каждому ненулевому биту будет прикреплен резервный рубль. Стало быть, за очистку любого бита дополнительно платить нам не придется: мы расплатимся за нее рублем, прикрепленным к этому биту в момент его установки.
Теперь легко определить учетную стоимость операции Increment. Поскольку каждая такая операция требует не более одной установки бита, ее учетную стоимость можно считать равной рублям. Следовательно, фактическая стоимость последовательных операций Increment, начинающихся с нуля, есть , поскольку она не превосходит суммы учетных стоимостей .
Анализ работы двоичного счетчика методом потенциалов. Проанализируем теперь трудоемкость -кратного выполнения операции Increment с помощью метода потенциалов.
Пусть — содержимое счетчика в начальный момент, — содержимое счетчика после выполнения -й операции, — число единиц в записи , — число единиц, превращенных в нули при -й операции. Очевидно, что
Пусть далее — реальная стоимость -й операции Increment, — ее учетная стоимость. Очевидно, что . Тогда
Если счет начинается с нуля, то
и
для всех . Поскольку сумма учетных стоимостей оценивает сверху сумму реальных стоимостей, имеем
то есть получаем, что суммарная стоимость операций есть с константой (двойкой), не зависящей от .
Метод потенциалов позволяет разобраться и со случаем, когда счет начинается не с нуля. В этом случае имеем
откуда при достаточно больших значениях () получаем, что реальная стоимость оценивается как , причем константа в -записи не зависит ни от , ни от начального значения счетчика.
Классы функций, используемые для оценки сложности алгоритмов
Все функции, используемые ниже для оценки сложности алгоритмов, считаются асимптотически неотрицательными функциями натурального аргумента, то есть неотрицательными, начиная с некоторого значения аргумента .
Для асимптотических оценок сверху используется класс функций
Для асимптотических оценок снизу используется класс функций
Для асимптотически точных оценок используется класс функций
Очевидно, что справедливы следующие соотношения
Далее, предполагается знание стандартных функций, используемых при оценках сложности, таких как полиномы, экспоненты, суперэкспоненты, логарифмы, суперлогарифмы, факториалы, числа Фибоначчи. Предполагается умение сравнивать их по скоростям роста.
Деревья и графы
Деревья находят широкое применение при проектировании алгоритмов и, в частности, структур данных. Отсылая читателя к литературе по теории графов, мы будем пользоваться такими понятиями, как узел, ребро, лист, потомок, сын, левый потомок, правый потомок, предок, отец, корень, ветвь и другие. Регулярным деревом назовем дерево, в котором фиксировано максимально возможное (как правило, небольшое) число потомков для каждого из его узлов. В частности, если число потомков для каждого узла не больше двух, то дерево называется бинарным, если не более трех — тернарным. Если это число может равняться только двум или трем, то дерево называется (—)-деревом.
Достаточно универсальным является способ представления регулярных деревьев, при котором каждый узел представляется записью, содержащей, кроме прикладной информации, позиции смежных с ним элементов, например позиции потомков или наряду с потомками позицию предка или еще каких-либо узлов, в зависимости от потребностей. Регулярность дерева позволяет фиксировать число полей, достаточное для представления любого узла.
Так, узлы бинарного корневого дерева можно представлять записями вида
где представляет связанную с узлом прикладную информацию, — позицию его левого потомка, а — позицию правого потомка. Само дерево в таком случае можно представить позицией его корня. Если в алгоритме необходимо продвижение от узла к предку, то узлы бинарного корневого дерева можно представлять записями вида
где — позиция предка рассматриваемого узла.
Для представления нерегулярных деревьев (то есть деревьев, узлы которых могут иметь произвольное число потомков) применяют следующий способ: потомки каждого узла нумеруются и каждый узел представляется записью, включающей в себя позицию его первого (левого) потомка и позицию его "правого брата".
Для регулярных деревьев более экономным по памяти может оказаться представление с помощью массива. Рассмотрим этот прием на примере бинарного дерева. Значения индексов массива отождествляются с узлами дерева, пронумерованными так, что корень получает номер 1, а потомки узла c номером получают номера и .
При таком представлении предок узла с номером будет иметь номер
(частное от деления на 2). Аналогично можно представить тернарное и другие регулярные деревья.
Остановимся вкратце на представлении графов общего вида. Обыкновенный граф с вершинами часто представляют матрицей смежности, то есть матрицей размером , в которой элемент, расположенный в -й строке и -м столбце, равен , если вершины графа с номерами , соединены ребром, и равен 0, если такого ребра нет. Если граф не ориентирован, то его матрица смежности симметрична и можно ограничиться хранением ее треугольной части.
Матричный способ представления может оказаться неэкономным с точки зрения использования памяти, если граф разрежен. Так, например, известно, что число ребер связного планарного графа с вершинами не превосходит величины () при , то есть оценивается величиной , а не как в общем случае . Представлять такие графы матрицей смежности, как правило, нецелесообразно.
Другой способ представления графа — это список или массив пар вершин, соответствующих ребрам. При таком способе, если граф не ориентирован, то из двух возможных пар (, ) и (, ) целесообразно хранить только одну, например ту, у которой первая компонента меньше второй.
Еще один способ, часто имеющий преимущества перед названными выше, — это представление графа массивом или списком списков (рис. 2.7).
Рис. 2.7. Представление графа комбинацией списков: множество вершин представлено списком узлов, к каждому из которых справа подцеплен список смежных с ним вершин
А именно, для каждой вершины организуется список смежных с ней вершин. В этом случае легко осуществляется доступ к окрестностям вершин. Примерно такого же эффекта можно достичь, представляя граф с помощью двух массивов: и , где — число ребер графа. Массив назовем адресным, а — информационным. В информационном массиве вначале перечисляются номера вершин, смежных с первой вершиной, затем — со второй и так далее. В адресном массиве указываются номера позиций информационного массива так, чтобы для каждой вершины по ним можно было находить фрагменты массива , в которых записаны номера вершин, смежных с этой вершиной.Например, может хранить позицию, с которой начинаются в массиве
вершины, смежные с -й, при этом
— первая позиция за пределами массива . В таком случае, если нам требуется с каждой вершиной из окрестности вершины выполнить оператор , то можно сделать это с помощью оператора цикла:
Заметим, что если граф не ориентирован, то каждое ребро (, ) будет представлено дважды: один раз в последовательности вершин, смежных с вершиной , а второй раз — в последовательности вершин, смежных с вершиной . Но эта избыточность часто бывает полезна с точки зрения времени выполнения операций над окрестностями вершин графа. Как недостаток такого представления графа, можно отметить неудобство при динамической модификации графа, например, добавление к графу ребра может потребовать большого количества пересылок в массиве . Этого недостатка лишен способ представления графа, показанный на рис. 2.7.
Моделирование списков с последовательным доступом при помощи массивов
Если использование динамических ссылок невозможно или нежелательно (тому могут быть свои причины), список со связями можно смоделировать при помощи массивов. В массиве хранятся элементы списка, то есть значения соответствующих полей узлов списка со связями. Позицией элемента является значение целочисленного индекса массива. Кроме того, вводится целочисленный массив , в котором для каждого узла списка указана позиция, где расположен его преемник. В качестве индексного пространства используем отрезок целочисленного типа.
В одних и тех же массивах и
могут размещаться сразу несколько списков, состоящих из узлов одного типа. С учетом такого возможного сосуществования различных списков их элементы могут размещаться в этих массивах хаотично, подобно тому, как узлы списков, представленных с помощью ссылок, могут произвольно располагаться в памяти компьютера.
На табл. 2.1 показано возможное заполнение массивов и
для одностороннего списка, представляющего кортеж
(пустые клетки не имеют отношения к этому списку).
| Адрес | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Inf | e | b | c | d | a | |||||||
| Next | 0 | 6 | 9 | 1 | 3 |
Доступ к списку можно осуществить через его первый элемент, позиция которого в массиве задается значением переменной . Значение говорит о том, что в позиции
расположен элемент, у которого нет преемника, то есть последний элемент кортежа.
На табл. 2.2 показано возможное заполнение массивов , и для представления кортежа () двусторонним списком.
| Адрес | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Inf | e | b | c | d | a | |||||||
| Next | 0 | 6 | 9 | 1 | 3 | |||||||
| Precede | 9 | 11 | 3 | 6 | 0 |
Основные отображения , , , , , задаются очевидным образом. Если какие-либо из них не заданы явно, то их можно вычислять через другие сканированием списка.
Чтобы одни и те же массивы , ,
использовать для одновременного хранения нескольких однотипных списков, позиции этих массивов объединяют в один так называемый свободный список . Это можно сделать, например, с помощью операторов
Массив при этом не заполняется. При создании новых списков используются элементы массивов , , , предварительно удаляемые из списка . В момент создания нового узла из списка
удаляется головной элемент, который и используется для добавления в новый список. С другой стороны, при удалении элемента из какого-либо списка освобождаемая позиция добавляется к свободному списку для последующего использования. Такая техника применялась, когда системы программирования не имели стандартных средств динамического выделения памяти. Однако в условиях ограниченной памяти этот прием можно использовать и сейчас. Дело в том, что при достаточно большом объеме оперативной памяти стандартные системы вынуждены использовать многоразрядную адресацию, в то время как для позиционирования в массивах , ,
можно задействовать малоразрядные представления чисел.
Некоторые дополнительные операции со связными списками
Конкатенация. Эта операция предназначена для соединения двух списков в один результирующий. Она эффективна в тех случаях, когда обеспечен доступ к последнему элементу списка с трудоемкостью . При соединении двух списков и первый элемент списка становится преемником последнего элемента списка . При этом возникают вопросы — должен ли получившийся список иметь какое-то новое имя и должны ли сохраниться как таковые исходные списки
и ?
В рассмотренной ниже процедуре Concat, реализующей операцию "Соединить два списка", принято следующее решение. К списку
присоединяется список , список сохраняется, а результирующим является список . Следует, однако, понимать, что если в список
будут внесены изменения, они автоматически произойдут в новом списке. Трудоемкость этой операции — .
Из списка удалить элементы, удовлетворяющие некоторому условию. Предположим, что требуемое условие на элемент
проверяется предикатом condition().
Построить список,состоящий из элементов данного списка , удовлетворяющих некоторому условию. Предположим, что требуемое условие на элементпроверяется предикатом condition().
Получить списокреверсированием списка
Общие сведения о списках
Остановимся на наиболее часто используемых структурах данных, называемых списками. Списки лежат в основе многих более сложных структур данных. В простейшем случае списки используются для представления кортежей.
Кортеж — это конечная последовательность, возможно с повторениями, элементов некоторого множества . Элементами кортежа могут быть числа, символы некоторого алфавита, точки плоскости и т.д. В более сложных случаях элементами кортежа, в свою очередь, могут быть также кортежи. Элементы, не являющиеся кортежами, называются атомами. Количество элементов в кортеже называется его длиной. Удобно рассматривать кортежи, не содержащие ни одного элемента. Такие кортежи называются пустыми. Длина пустого кортежа считается равной .
Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и содержанием, то есть элементом множества . Если длина кортежа равна , , то кортеж
удобно рассматривать как отображение множества в множество . Таким образом, — это -й элемент кортежа .
Термин "список" используется как обобщающее название различных структур данных, используемых для представления кортежей в памяти компьютера. При представлении кортежа в памяти появляется еще одна характеристика элемента кортежа — его позиция в памяти. В некоторых случаях номер элемента в кортеже и его позиция в памяти связаны друг с другом арифметическими соотношениями таким образом, что по номеру легко вычисляется позиция и, наоборот, по позиции вычисляется номер. В других случаях связь между номерами и позициями задается "таблично" или осуществляется с помощью алгоритмических процедур. Множество позиций обозначим через . Иногда удобно считать, что в множестве имеется специальный элемент , указывающий на несуществующую область памяти. Таким образом, при рассмотрении того или иного списка мы имеем дело с тремя множествами , , и с отображениями на этих множествах.
Типичными при работе со списками являются следующие операции:
Нахождение позиции элемента в памяти по его номеру в кортеже.Нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции.Нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции.Удаление элемента, находящегося в заданной позиции.Вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции.Определение длины кортежа.
При описании этих и других операций со списками будем использовать следующие отображения и константы, заданные на множествах , , :
: , где (pos) — элемент списка, находящийся в позиции pos памяти., где (pos) — позиция элемента, следующего за элементом из позиции pos.: , где (pos) — позиция элемента, находящегося перед элементом из позиции pos.: , где (pos) — кортежный номер элемента, находящегося в позиции pos.: , где () — позиция элемента, имеющего кортежный номер . — длина списка. — позиция первого элемента списка. — позиция последнего элемента списка.
Иногда для распознавания концевых элементов списка пользуются следующим соглашением: eсли pos является позицией последнего элемента списка, то полагают , а если началом, то . В случаях, когда позицией элемента, следующего за последним или предшествующего первому, является несуществующая позиция , будем считать, что принадлежит множеству . При изменении содержимого списка все введенные множества, отображения и константы могут изменяться.
Различные представления кортежей с помощью списковых структур характеризуются степенью эффективности выполнения тех или иных операций. Так, при одном представлении эффективно вычисляется порядковый номер элемента по его позиции, но менее эффективно осуществляется вставка нового элемента. При другом представлении легко осуществляется вставка, а определение порядкового номера элемента по его позиции требует довольно много времени, например пропорционально длине списка. К сожалению, не всегда удается найти способ представления кортежей, для которого все используемые в конкретном алгоритме операции одинаково эффективны. Поэтому выбор структуры для представления кортежа сопряжен с анализом алгоритма, а именно, с выяснением того, какие операции, в конечном счете, определяют его суммарную трудоемкость. В зависимости от набора операций, которые предполагается выполнять со списками, выделяют некоторые их разновидности.
Список, в который предполагается добавлять и удалять элементы лишь с одного его конца, называется стеком.
Если добавление элементов должно происходить с одного конца, а удаление — с другого, то такой список называется очередью. Если удалять и добавлять элементы можно с любого конца списка, то такой список называется деком. Если добавлять можно с любого конца, а удалять только с одного, то список называется деком с ограниченным выходом. Списки более общего вида позволяют включать и удалять элементы из любой позиции. Списки классифицируются также по возможностям их сканирования (просмотра) в одном направлении (от начала к концу или от конца к началу) или в обоих направлениях. В первом случае список называется односторонним, во втором — двусторонним.
Списки, для которых не планируется выполнять операции вставки
удаления из произвольной позиции, удобно представлять массивами. В этом случае кортежный номер элемента можно либо отождествить с номером элемента в массиве, либо сделать легко вычисляемым по этому номеру. Такие списки называют списками с прямым доступом к элементам. Другими словами, под прямым доступом мы понимаем возможность по номеру элемента в кортеже за единицу времени определять как сам элемент, так и его позицию в памяти.
При представлении кортежей, для которых планируется выполнение операций вставкиудаления элемента из произвольной позиции, используется возможность нахождения программным путем свободного пространства в памяти для размещения вставляемого элемента. При использовании языков программирования высокого уровня эти обязанности обычно берет на себя система программирования (оператор new — в языках PASCAL и C). При вставлении нового элемента в список место, куда он вставляется, указывается с помощью косвенной адресации. Это может быть адрес элемента, перед которым либо после которого вставляется новый элемент, либо и тот, и другой. Такой способ дает возможность лишь последовательного доступа к элементам. Другими словами, при последовательном доступе гарантируется определение за единицу времени позиции очередного элемента лишь по позиции предыдущего или следующего за ним элемента, но не по его номеру в кортеже.
Отметим еще, что при конструировании списков иногда удобно элементами списка считать не сами элементы множества , а их позиции в памяти. В этом случае списки, по терминологии Р.Тарьяна, называются экзогенными (внешними), в противном случае — эндогенными (внутренними). Экзогенный способ используют в тех случаях, когда элементы множества для своего представления требуют много пространства и переписывание элемента из одного участка памяти в другой сопряжено с большими затратами времени.
Преимущество использования экзогенных списков может ярко проявиться в такой задаче, как сортировка (упорядочение) элементов списка в порядке возрастания или убывания некоторой числовой характеристики, называемой ключом элемента. Основными операциями при сортировке, определяющими ее трудоемкость, являются операция сравнения ключей и операция перемещения элементов. Очевидно, что при эндогенном способе представления списка суммарные затраты времени на перемещение элементов могут оказаться намного больше, чем при экзогенном способе.
При описании операций над списками будем считать, что каждый из них описан с помощью дескриптора, имеющего форму записи, состоящей из нескольких полей. Дескриптор предназначен для того, чтобы явно указать составные части, из которых формируется список. Как правило, в дескриптор будет входить поле , содержащее позицию первого элемента. Если в конструкции списка используется некоторый массив, то в дескрипторе указывается имя этого массива.
Поля, относящиеся к конкретному списку , будем записывать в форме
В полях дескриптора будем указывать также имена процедур и функций, которые реализуют примитивные операции над списками при рассматриваемой их реализации.
Так, например, дескриптор списка может иметь форму
При таком дескрипторе
означает позицию первого элемента списка , — его длину.
Списки с последовательным доступом
Последовательный доступ к элементам списка, как правило, реализуется с использованием динамического выделения памяти во время исполнения программы. Поиск свободных участков памяти обычно возлагается на систему программирования. Мы будем называть такие списки связными. Преимущества связных списков перед списками с прямым доступом проявляются в тех случаях, когда часто используются вставки в списки и удаление элементов из списков. Еще одно преимущество динамического выделения памяти может проявиться, когда в алгоритме одновременно используется большое количество списков, каждый из которых в процессе работы может потребовать большой объем памяти, однако в совокупности эта память может быть ограничена приемлемой величиной.
Элементы связного списка, следующие друг за другом, не обязательно размещаются в последовательных ячейках памяти — доступ к следующему и предыдущему элементам осуществляется при помощи специальных ссылок (указателей). Чтобы обеспечить запоминание указателей на следующий и предыдущий элементы, каждый элемент списка "погружается" в узел, для которого в памяти компьютера формируется запись, состоящая из нескольких полей. В простейшем случае эта запись может состоять из двух полей. Одно из них — — предназначено для запоминания самого элемента, а другое — — для запоминания позиции следующего. Для обозначения такого узла будем использовать следующую форму:
где — позиция (адрес) узла в памяти. Поскольку у последнего элемента нет следующего, его поле заполняют значением . Иногда вместо используют ссылку на сам этот элемент, что также может являться признаком конца списка. Мы часто будем пользоваться именно этим способом распознавания конца списка. Представление списка с помощью таких узлов обеспечивает сканирование списка от начала к его концу. Доступ к самому списку осуществляется через его голову с помощью переменной , содержащей позицию первого элемента. Такие списки называются односторонними.
При описании операций со списками через будем обозначать узел, расположенный в позиции .
Для доступа к полям узла
используем форму ,
и т.д. Оператор для создания нового узла будем записывать в виде
Для обеспечения сканирования как от начала к концу, так и от конца к началу используют узлы следующего вида:
Поле служит для запоминания позиции элемента, предшествующего элементу, находящемуся в позиции . Доступ к такому списку может осуществляться как через его начало с помощью переменной , так и через конец с помощью переменной . Такие списки называются двусторонними.
На рис. 2.1—2.6 представлено несколько разновидностей списков. Узлы списков изображены прямоугольниками, разделенными на части по числу полей. Стрелки проведены в соответствии со значениями полей и .
Рис. 2.1. Односторонний список: вход через первый элемент, сканирование от начала к концу, признак конца — Next(pos) = nil
Рис. 2.2. Односторонний список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = pos
Рис. 2.3. Односторонний циклический список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = first
Рис. 2.4. Односторонний циклический список: вход через последний элемент с помощью ссылки Last^.next; сканирование от начала к концу, признак конца — pos = last
Рис. 2.5. Двусторонний список: вход через первый элемент, сканирование от начала к концу и от конца к началу; признак начала — Procede(pos) = nil; признак конца — Next(pos) = nil
Рис. 2.6. Двусторонний циклический список: вход через первый элемент; сканирование от начала к концу и от конца к началу, признак конца — Next(pos) = first
При ее использовании могут возникнуть проблемы, связанные с некорректным обращением, так как в процедуре не производится проверка, является ли позиция pos позицией какого-либо элемента списка . Ответственность за некорректное обращение несет вызывающая программа. Проверка этого условия с помощью сканирования списка могла бы оказаться слишком дорогой и свела бы на нет преимущества использования связных списков. Еще одна проблема, связанная с выполнением этой операции, заключается в том, что узел
может оказаться недоступным при потере значения переменной pos, но память будет оставаться занятой. Если это нежелательно, следует, воспользовавшись системными средствами, освободить занимаемую узлом память. Замечания по поводу некорректного обращения будут справедливы и для некоторых следующих процедур, однако мы не будем каждый раз напоминать об этом.
Вставить в список элемент после элемента, находящегося в позиции
Следующие две операции рассмотрим на примере одностороннего циклического списка (см. рис. 2.4).
Добавить элемент к концу списка
Добавить элемент к началу списка
Следующие три процедуры рассмотрим на примере двустороннего циклического списка (см. рис. 2.6).
Удалить последний элемент списка
Удалить первый элемент списка
Удалить из списка элемент, находящийся в позиции
Списки с прямым доступом
Прямой доступ, как правило, реализуется при представлении списка массивом. Элементы кортежа размещаются в идущих подряд ячейках некоторого массива. Для локализации списка в массиве введем целочисленную переменную для хранения номера позиции массива, в которой расположен его первый элемент, и целочисленную переменную , означающую длину списка. Равенство служит признаком того, что массив содержит пустой список. Иногда для переменных, хранящих позицию элемента массива, удобно иметь какое-либо условное значение, выходящее за рамки индексации массива. Будем обозначать его .
Рассмотрим подробнее реализацию списка с прямым доступом, дающую возможность добавлять элементы к списку с любого его конца. Воспользуемся циклической "нумерацией" элементов массива, при которой следующим за последним элементом массива считается его первый элемент, а предыдущим для первого — последний (речь идет об элементах массива, а не об элементах списка). Если элементы массива пронумеровать числами от
до , то переход к следующему (предыдущему) элементу списка осуществляется с помощью прибавления (вычитания) единицы по модулю , где — длина массива. Дескриптор такого списка будет иметь форму
Добавление элемента к началу списка осуществляется его записью в позицию
с последующим присваиванием , а добавление в конец (записью элемента в позицию (
с последующим выполнением оператора . Заметим, что при таком способе начальный фрагмент кортежа может оказаться в конце массива, а конечный фрагмент — в начале. Заметим также, что добавление нового элемента возможно только при условии . Кроме того, нужно иметь в виду, что в системах программирования со статическим распределением памяти под массивы, которое происходит во время компиляции, длину массива следует выбирать достаточной для размещения списков, порождаемых разрабатываемым алгоритмом. Следует помнить, что максимальная длина списка зависит не только от алгоритма, но и от входных данных.
Основные отображения для списка с прямым доступом, имеющего дескриптор , определяются следующим образом:
Приведем несколько процедур для работы со списками с прямым доступом.
Создать пустой список
Добавить элемент к концу списка
Добавить элемент e к началу списка
Заменить элемент с кортежным номером
на элемент
Удалить последний элемент списка
Удалить первый элемент списка
Анализ трудоемкости
Для анализа трудоемкости выполнения операций нам потребуются две функции. Одна из них,, является суперэкспонентой и определяется следующим образом:
Вторая — суперлогарифм , по основанию 2, определяемая соотношением
Суперлогарифм является в некотором смысле обратной функцией к суперэкспоненте, . Значения функций и при нескольких значениях аргументов приведены в следующих таблицах:
| … | ||||||||||||||
Ребропри текущем состоянии коллекции назовем корневым, если— корень и (петля); назовем его прикорневым, если — корень и, в противном случае — внутренним.
Отметим следующие свойства коллекции на множестве из элементов. Прикорневое ребро может превратиться во внутреннее, а корневое — в прикорневое только при выполнении операции ОБЪЕДИНИТЬ.
Внутреннее ребропри первом же выполнении операции НАЙТИ, "проходящей через него", исчезает, но вместо него появляется прикорневое ребро, при этом, следовательно, внутреннее ребро "участвует в поиске" не более одного раза.
Если при выполнении очередной операции ОБЪЕДИНИТЬузел становится родителем узла , то после ее выполнения справедливо неравенство.
При выполнении операции НАЙТИ ранги узлов не изменяются, но узлы могут менять своих родителей, то есть меняется структура леса.
Если перед выполнением операции НАЙТИ узел был родителем узла , а после выполнения этой операции родителем узла стал узел , то выполняется неравенство. Следовательно, даже после изменения леса в результате выполнения операции НАЙТИ ранги вдоль любого пути от листа к корню будут строго возрастать.
При выполнении операции ОБЪЕДИНИТЬ ранг любого некорневого элемента не изменяется, а ранг корня либо сохраняется, либо увеличивается на 1.
Остается оценить суммарную трудоемкость операций НАЙТИ.
Черезобозначим ранг узла , который получится после выполнения операции, а — родитель узла, получающийся после выполнения этой операции. Определим множество Для краткости будем обозначать .
Поскольку ранг узла может увеличиваться лишь при выполнении операции ОБЪЕДИНИТЬ, причем не более чем на 1, после таких операций ранг никакого узла не может стать больше , следовательно, максимальный индекс , при котором может быть непустым, равен .
Оценим теперь суммарное время, требуемое для выполнения операций НАЙТИ; очевидно, оно пропорционально числу ребер, ведущих от сыновей к отцам и встречающихся при выполнении всех таких операций. Для оценки времени, затрачиваемого на реализацию этих операций, применим бухгалтерский прием. Отнесем расход времени на прохождение очередного ребра от узла к его родителю при выполнении операции типа НАЙТИ на одну из трех разных статей расходов: "корневую", "транзитную" и "местную" в зависимости от следующих условий.
Еслии в данный момент не является корнем, то расходы относим на статью транзитных расходов. Еслии не является корнем, то на статьюместных расходов в-м диапазоне, если же— корень, то на статью корневых расходов.
Сумму местных расходов во всех диапазонах обозначим через
Имеем, так как при каждом выполнении операции НАЙТИ проходится одно корневое и, возможно, одно прикорневое ребро.
Для транзитных переходов имеем, так как при каждом выполнении операции НАЙТИ происходит не болеепереходов из одного диапазона в другой.
Для оценки величины введем потенциалузла после выполнения операции . Если к узлу еще не применялась операция СОЗДАТЬ, то.
Потенциалом группыпри текущем состоянии коллекции назовем величину
Очевидно, что в любой момент времени справедливо неравенство
(1) |
Операции над разделенными множествами
Разделенные множества — это абстрактный тип данных, предназначенный для представления коллекции, состоящей из некоторого числа попарно непересекающихся подмножеств
заданного множества . Для простоты в качестве
будем рассматривать множество .
Этот тип данных применяется в таких задачах, как поиск минимального остовного дерева для заданного взвешенного неориентированного графа, построение компонент связности графа, минимизация конечного автомата, и многих других, требующих динамического поддержания некоторого отношения эквивалентности. Примеры таких задач будут рассмотрены ниже.
Как правило, в таких задачах вычисления начинаются с пустой коллекции подмножеств (). Затем по мере вычислений формируются новые подмножества, включаемые в коллекцию. Формирование новых подмножеств происходит либо путем создания одноэлементного подмножества, либо путем объединения уже существующих в коллекции подмножеств. Для осуществления таких действий используются имена включенных в коллекцию подмножеств. В качестве имени подмножества будем использовать один из его элементов (главный элемент), выбираемый по определенному правилу. Поскольку в коллекции всегда будут находиться попарно непересекающиеся подмножества множества , такое имя будет однозначно определять требуемое подмножество.
СОЗДАТЬ(). Эта операция предназначена для введения в коллекцию нового подмножества, состоящего из одного элемента , при этом предполагается, что не входит ни в одно из подмножеств коллекции, созданной к моменту выполнения этой операции. Элемент указывается в качестве параметра. Именем созданного подмножества будет считаться сам элемент .
ОБЪЕДИНИТЬ(). С помощью этой операции можно объединить два подмножества коллекции, имеющие, соответственно, имена и , в одно новое подмножество, при этом оба объединяемые подмножества удаляются из коллекции, а вновь построенное подмножество получает некоторое имя. Во всех рассматриваемых нами случаях именем нового полученного в результате этой операции подмножества будет одно из имен или .
Имена объединяемых подмножеств указываются в качестве параметров.
НАЙТИ(). Эта операция позволяет определить имя
того подмножества коллекции, которому принадлежит элемент . Если элемент до выполнения операции не входил ни в одно из подмножеств коллекции, то в качестве берется 0.
Последовательность , составленную из операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ, назовем корректной, если перед выполнением каждой операции из последовательности соблюдены условия ее применения. Например, перед выполнением очередной операции вида ОБЪЕДИНИТЬ (, ) подмножества с именами и должны быть уже созданы. Перед выполнением операции СОЗДАТЬ() элемент не должен принадлежать ни одному из подмножеств коллекции. Операция НАЙТИ (, ) применима при любом значении аргумента . Следует только помнить, что если не принадлежит ни одному из подмножеств коллекции, то получим .
Мы рассмотрим несколько способов представления коллекции разделенных множеств в памяти компьютера и алгоритмической реализации перечисленных операций. А именно, будут описаны представления
с помощью массива;с помощью древовидной структуры;с помощью древовидной структуры с использованием рангов вершин;с помощью древовидной структуры с использованием рангов вершин и сжатия путей.
Последний из перечисленных способов является наиболее эффективным по времени выполнения произвольных корректных последовательностей операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ. Строго говоря, во всех перечисленных случаях будут использоваться массивы, но интерпретации их содержимого будут различными. Каждый раз при описании очередной реализации мы будем обсуждать оценки трудоемкости рассматриваемых операций.
Представление разделенных множеств древовидной структурой
Пусть, по-прежнему, — множество, из элементов которого будет строиться коллекция. Каждое подмножество коллекции представляется корневым деревом, узлы которого являются элементами этого подмножества, то есть отождествляются с номерами из множества . Корень дерева используется в качестве имени соответствующего подмножества (канонический элемент). Для каждого узла дерева определяется узел , являющийся его родителем в дереве; если — корень, то полагаем .
Фактически в памяти компьютера это дерево будем представлять массивом так, что будет предком узла , если не является корнем, и , если — корень. Если же не входит ни в одно из подмножеств коллекции, то .
Рассмотрим пример. Пусть и коллекция состоит из двух подмножеств и . Деревья, представляющие эти подмножества, могут быть такими, как на рис.3.1. Кружочки обозначают узлы дерева; указатели на родителей представлены при помощи стрелок. Именем одного из этих подмножеств является 3, другого — 6:
Рис. 3.1.
Представление разделенных множеств с использованием рангов вершин
Предыдущую реализацию разделенных множеств можно усовершенствовать следующим образом. Операцию ОБЪЕДИНИТЬ можно выполнить так, чтобы высота дерева, соответствующего объединению двух множеств, была как можно меньше. А именно, корень большего по высоте дерева сделать родителем корня другого дерева. Назовем такую реализацию операции ОБЪЕДИНИТЬ объединением по рангу. В качестве ранга в данном случае берется высота соответствующего дерева.
Представление разделенных множеств с помощью массива
Пусть — множество, из элементов которого будет строиться коллекция разделенных подмножеств. Одним из очевидных способов представления коллекции является представление ее с помощью массива. При таком способе для каждого элемента
в соответствующей (-й) ячейке массива помещаем имя (канонический элемент) того подмножества, которому принадлежит элемент . Если элемент
не принадлежит ни одному из подмножеств коллекции, то в -ю ячейку записываем 0.
Примеры использования разделенных множеств
Пример 1.
Рассмотрим задачу выделения компонент связности неориентированного графа. Напомним, что компонентой связности называется максимальное по включению подмножество вершин графа такое, что любые две его вершины связаны цепью. Полагаем, что вершины графа пронумерованы числами и каждое ребро представлено парой () номеров вершин. Предполагаем также, что множество ребер не пусто.
Алгоритм выделения компонент связности неориентированного графа
Очевидно, построенные подмножества коллекции будут представлять искомые компоненты связности. Используя названия основных операций над коллекцией разделенных множеств, представленный выше алгоритм можно записать в следующем виде:
Пример 2.
Рассмотрим неориентированный связный граф без петель, ребрам которого приписаны в качестве весов положительные вещественные числа. Требуется построить остовное дерево, накрывающее все вершины графа и имеющее минимальный суммарный вес входящих в него ребер. Итак, пусть заданный граф имеет множество вершин, пронумерованных числами , и множество ребер. Каждому ребру из множества
поставлена в соответствие пара его концевых вершин и число — его вес. Для решения этой задачи были предложены различные алгоритмы. Мы рассмотрим алгоритм, который разработал Крускал.
Алгоритм Крускала
Заметим, что в процессе работы алгоритма в множестве будут находиться ребра, составляющие ациклический подграф исходного графа, являющийся лесом, состоящим из некоторого числа деревьев. Отсутствие циклов гарантируется проверкой "Если " в пункте 6 описанного алгоритма. Фактически при происходит объединение двух поддеревьев в одно дерево с помощью ребра , найденного на шаге 3.
Если исходный граф связен, как сказано в постановке задачи, то построенное с помощью такого алгоритма множество будет, очевидно, представлять дерево, накрывающее все вершины исходного графа. Доказательство того, что суммарный вес входящих в него ребер будет минимальным, можно найти в разделе "Графы".
В алгоритме естественным образом используется структура разделенных множеств. Обратим внимание на операцию поиска в множестве
ребра
с минимальным весом. Эффективность этой операции во многом зависит от выбора структуры данных для хранения множества . Приемы эффективного выполнения этой операции рассмотрены в разделе "Приоритетные очереди".
Реализация операций с использованием рангов вершин
Для такой реализации разделенных множеств необходимо хранить с каждым узлом дополнительно еще одну величину — высоту поддерева, корнем которого является узел . Будем называть ее высотой, или рангом, узла . Остальные операции нужно настроить на корректную работу с этим полем. Будем хранить высоту каждого узла в ячейке массива .
Операция СОЗДАТЬ () назначает в качестве родителя узлатот же самый, а высотой узласчитает 0. Таким образом, время выполнения данной операции есть. В результате выполнения операции СОЗДАТЬ () образуется новое дерево, изображенное на рис. 3.6. Число, расположенное рядом с узлом, обозначает его высоту. Описанные действия реализуются с помощью операторов
Рис. 3.6.
Операция ОБЪЕДИНИТЬ
() назначает корень большего по высоте дерева родителем корня другого дерева. Если деревья имеют одинаковую высоту, то узел назначается родителем узла , после чего значение высоты узла увеличивается на единицу. Заметим, что и должны быть до выполнения операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет имя того из объединяемых подмножеств, у которого корень имел большую высоту, а имя другого из объединяемых подмножеств перестанет быть именем какого-либо из подмножеств. Очевидно, время выполнения этой операции есть константа. Выполнить описанные действия можно с помощью следующей процедуры:
На рис. 3.7 и рис. 3.8 показано применение операции ОБЪЕДИНИТЬк коллекции, изображенной на рис. 3.3, с учетом высот объединяемых поддеревьев. Рядом с кружочками, изображающими узлы, показаны их высоты. Так как, то родителем узла 6 становится узел 3.
Операция НАЙТИ () осуществляется, как и в предыдущей реализации, продвижением по указателям на родителей от узла до корня дерева. В качестве берется найденный корень.
Рис. 3.7.
Рис. 3.8.
Очевидно, что время выполнения данной операции, как и ранее, пропорционально длине пути из узлав корень соответствующего дерева. Однако длина такого пути в данном случае может быть оценена иначе. Для оценки длины этого пути докажем следующие леммы:
Лемма 1.
В результате выполнения любой последовательности операций из набораСОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИнад пустой коллекцией разделенных множеств для любого узла выполняется неравенство, где — количество узлов в поддереве с корнем — высота узла .
Доказательство
Очевидно, перед первым применением операции ОБЪЕДИНИТЬ для любого узлаимели ,и, следовательно,. Операции СОЗДАТЬ и НАЙТИ не могут нарушить доказываемого неравенства, поэтому доказательство можно провести индукцией по количеству применений операции ОБЪЕДИНИТЬ.
Предположим, что перед очередным применением операции ОБЪЕДИНИТЬ () доказываемое неравенство все еще остается верным, тогда если высота узла меньше высоты узла , то дерево, полученное с помощью ОБЪЕДИНИТЬ (), имеет корень , а высоты узлов и не изменились. Количество узлов в дереве с корнем не изменилось, а количество узлов в дереве с корнем увеличилось. Таким образом, как для узлов,, так и для всех остальных неравенство сохраняется. Случай, когда высота узла больше высоты узла , аналогичен рассмотренному.
Если же высоты деревьев с корнями и до выполнения операции были одинаковы (, то узел становится родителем узла , высота узла увеличивается на 1, а высота узла не изменяется. Пусть после выполнения операции величины,,,становятся равными соответственно,,,, тогда имеем,,,. По предположению индукции, имеем и. Следовательно, после выполнения рассматриваемой операции для узлов и имеем соотношения Таким образом, утверждение леммы остается верным и в этом случае.
Лемма 2.
Если за время работы, начавшейся с пустой коллекции, операция СОЗДАТЬ применяласьраз, то для любогочисло узлов высоты удовлетворяет неравенству.
Доказательство
Пусть— все узлы высоты , тогда по лемме 1 присправедливы неравенства. Таким образом, откуда и следует требуемое неравенство.
Следствие 3.
В результате выполнения любой последовательности операций из набораСОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИнад пустой коллекцией разделенных множеств для любого узлаимеет место неравенство.
Доказательство
Дерево максимальной высоты образуется, очевидно, лишь тогда, когда все элементов объединяются в одно множество. Для такого дерева количество узлов максимальной высоты равно 1, по лемме 2 имеем , откуда и, следовательно,.
Следствие 4.
Время выполнения операции НАЙТИ есть.
Следствие 5.
При реализации разделенных множеств с использованием рангов время выполнения операций ОБЪЕДИНИТЬ иили НАЙТИ есть величина.
Замечание
При реализации операции объединения подмножеств в качестве ранга узла можно использовать количество узлов в поддереве с корнем в данном узле. Утверждение леммы 1 будет справедливым и в этом случае, следовательно, сохранятся и оценки времени выполнения операций.
Реализация операций с помощью древовидной структуры
Операция СОЗДАТЬ
() назначает в качестве родителя узла сам узел с помощью присваивания . Таким образом, время выполнения операции есть . В результате выполнения операции СОЗДАТЬ() образуется новое одновершинное дерево с петлей в корне, изображенное на рис. 3.2.
Рис. 3.2.
Если к коллекции подмножеств, изображенных на рис. 3.1, применить операцию СОЗДАТЬ (5), то получим коллекцию, изображенную на рис. 3.3.
Рис. 3.3.
Операция ОБЪЕДИНИТЬ
() назначает узел
родителем узла с помощью присваивания . Заметим, что и должны быть до выполнения рассматриваемой операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет , а перестанет быть именем какого-либо множества. Время выполнения этой операции есть .
Рис. 3.4.
Если применить операцию ОБЪЕДИНИТЬ к коллекции, представленной на рис. 3.3, то получим коллекцию, состоящую из двух подмножеств и , — изображенную на рис. 3.4. Именем первого из этих подмножеств будет 6, второго — 5.
Операция НАЙТИ() осуществляется продвижением по указателям на родителей от узла до корня дерева. В качестве берется этот корень. Описанные действия можно реализовать с помощью операторов
Очевидно, что время выполнения данной операции есть , где — длина пути из узла в корень соответствующего дерева. Но заметим, что при выполнении операций СОЗДАТЬ и ОБЪЕДИНИТЬ возможно образование дерева в виде линейной цепочки из узлов, изображенной на рис. 3.5.
Рис. 3.5.
К такой цепочке может привести, например, следующая последовательность операций
СОЗДАТЬ ();
СОЗДАТЬ ();
… … …
СОЗДАТЬ ();
ОБЪЕДИНИТЬ ();
ОБЪЕДИНИТЬ ();
… … …
ОБЪЕДИНИТЬ ();
Как видим,может достигать величины, поэтому трудоемкость операции НАЙТИ является величиной.
Худший случай применения операции НАЙТИ в данной ситуации — это НАЙТИ (). В этом случае необходимо сделатьпереход по ссылкам на родителей, чтобы дойти от узла к корню дерева , и один переход, чтобы узнать, что родитель узла есть сам узел .
Если операция СОЗДАТЬ выполняетсяраз, то время выполнения последовательности, составленной изопераций ОБЪЕДИНИТЬ иили НАЙТИ, при рассматриваемой реализации разделенных множеств есть величина . Действительно, время выполнения операций ОБЪЕДИНИТЬ, очевидно, есть , так как время выполнения одной такой операции есть константа. Время выполнения операций НАЙТИ есть, так как время выполнения одной такой операции есть. Итак, время выполнения произвольных операций есть .
Реализация операций с помощью массива
Обозначим через массив длины , с помощью которого будем представлять коллекцию. Пустая коллекция представляется массивом, заполненным нулями.
Операция СОЗДАТЬ() осуществляется записью элемента
в ячейку с номером . Время выполнения операции — .
Операция ОБЪЕДИНИТЬ() осуществляется следующим образом. Просматриваются элементы массива , и в те ячейки, в которых было записано имя , заносится новое имя — . Следовательно, именем вновь образованного подмножества будет , а перестанет быть именем какого-либо подмножества. Очевидно, время выполнения этой операции — .
Операция НАЙТИ () выдает в качестве
содержимое элемента с номером в массиве . Время выполнения операции — .
При такой реализации разделенных множеств, очевидно, что время выполнения произвольных операций, среди которых операций ОБЪЕДИНИТЬ, есть величина .
Сводные данные о сложности операций с разделенными множествами
Реализация с помощью массива
| СОЗДАТЬ | |
| ОБЪЕДИНИТЬ | |
| НАЙТИ | |
| операций |
Реализация с помощью древовидной cтруктуры
| СОЗДАТЬ | |
| ОБЪЕДИНИТЬ | |
| НАЙТИ | |
| операций |
Реализация с использованием рангов вершин
| СОЗДАТЬ | |
| ОБЪЕДИНИТЬ | |
| НАЙТИ | |
| операций |
Реализация с использованием рангов и сжатия путей
| СОЗДАТЬ | |
| ОБЪЕДИНИТЬ | |
| НАЙТИ | |
| операций | |
Алгоритм Дейкстры
- Заполнить массив нулями.Каждой вершине приписать в качестве ключа — максимально возможное число (оно должно быть больше, чем длина наибольшего из кратчайших путей в графе; в процессе вычислений это число будет уменьшаться и в итоге заменится на длину кратчайшего пути из вершины в вершину ).Организовать приоритетную очередь из вершин графа, взяв в качестве ключей величины , .Заменить ключ вершины на 0.Пока очередь не пуста, выполнять операции .Выбрать (с удалением) из приоритетной очереди элемент с минимальным ключом.Для каждой вершины , смежной с , выполнить операции .Вычислить величину .Если , то уменьшить ключ элемента
на величину и заменить старое значение величины на .
Упражнение
Напишите на каком-либо алгоритмическом языке реализацию алгоритма Дейкстры с использованием -кучи и испытайте ее на тестовых примерах при различных значениях .
Бесхитростная сортировка в памяти с прямым доступом.
Бесхитростный алгоритм сортировки может заключаться в выполнении следующих операторов:
Здесь — процедура, транспонирующая элементы . Заметим, что число сравнений
при реализации такого алгоритма равно . В частности, это означает, что время работы алгоритма равно .
Нахождение кратчайших путей в графе
Входные данные:
Граф со взвешенными ребрами (под весами можно понимать длины ребер, если речь идет о геометрическом графе, или любые другие числовые характеристики ребер). Пусть — вес ребра ().Стартовая вершина (вершина, от которой вычисляются расстояния до всех остальных вершин).
Выходные данные:
Массив , — кратчайшее расстояние от вершины до вершины ).Массив , — предпоследняя вершина в кратчайшем пути из вершины
в вершину ).
Приводимый ниже алгоритм Дейкстры корректно решает задачу для графов с неотрицательными весами вершин. Если же в графе есть ребра с отрицательными весами, но нет циклов с отрицательным суммарным весом, то для решения задачи можно использовать алгоритм Форда, Беллмана.
Операции с d-кучей
При реализации основных операций над кучами используются две вспомогательные операции — ВСПЛЫТИЕ и ПОГРУЖЕНИЕ. При реализации этих операций введем еще одну вспомогательную операцию — транспонирование, с помощью которой будем менять местами элементы, расположенные в двух разных узлах дерева. Ее реализация может быть представлена следующим образом:
Замечание.
Если в кучу помещаются только ключи элементов, то процедура транспонирования модифицируется соответствующим образом.
Операция ВСПЛЫТИЕ.Эта операция применяется в тех случаях, когда в некотором узле, например в -м, расположен элемент , нарушающий кучеобразный порядок так, что его ключ меньше ключа его родителя .
Элементы и меняются местами. Если после этого элемент
снова не удовлетворяет условиям кучи, то еще раз проводится аналогичная перестановка. И так до тех пор, пока не встанет на свое место.
Рассмотрим 3-дерево на рис. 4.3. В этом дереве кучеобразный порядок нарушает узел с ключом , так как его родительскому узлу приписан элемент с ключом .
Рис. 4.3.
Применим к узлу операцию ВСПЛЫТИЕ. Элементы с ключами и меняются местами. В результате получается дерево, представленное на рис. 4.4.
Рис. 4.4.
Теперь нарушен кучеобразный порядок в узле (), меняем местами элементы c ключами и . В результате получаем кучу, изображенную на рис. 4.5. Кучеобразный порядок восстановлен, операция ВСПЛЫТИЕ завершена.
Рис. 4.5.
Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Это число, очевидно, не более чем удвоенное число узлов в пути от узла до корня дерева. Длина такого пути в -куче с узлами не превосходит ее высоты, а именно , в соответствии с доказанным выше утверждением 1. Значит, время выполнения данной операции — .
Реализация операции ВСПЛЫТИЕ. Входным параметром этой операции является номер узла, в котором нарушен порядок:
Замечание.
- Операцию ВСПЛЫТИЕ можно применять не только к -куче, но и к другим видам куч.Для более эффективного выполнения операции ВСПЛЫТИЕ можно поступить следующим образом: запомнить элемент, находящийся в узле , переместить элемент из его родительского узла
в узел , затем из узла в узел
и так до тех пор, пока не освободится узел для запомненного элемента. После этого поместить запомненный элемент на освободившееся место. Более точно это можно выразить с помощью следующих операторов:
Операция ПОГРУЖЕНИЕ. Эта операция также применяется для восстановления свойства кучеобразности. Пусть, например, в -м узле расположен элемент , нарушающий кучеобразный порядок таким образом, что ключ элемента больше ключа элемента , приписанного потомку узла . В этом случае среди непосредственных потомков узла выбирается элемент с наименьшим ключом, и элементы и меняются местами. Если после этого элемент снова не удовлетворяет условиям кучи, то еще раз проводим аналогичную перестановку. И так до тех пор, пока не встанет на свое место.
Рассмотрим -дерево, представленное на рис. 4.6. В узле расположен элемент с ключом , и этот узел имеет двух потомков с меньшими ключами, а именно и . Применим к элементу
операцию ПОГРУЖЕНИЕ.
Рис. 4.6.
Если у узла нет потомков, то .
Реализация операции ПОГРУЖЕНИЕ
Операция ВСТАВКА. Если перед выполнением этой операции куча содержала узлов (напомним, что они пронумерованы числами от
до ), то добавляем к дереву -й узел (его номер будет ) и приписываем ему элемент с именем и ключом . Вставка нового элемента производится посредством отведения для него места в -ых позициях массивов и соответственно, после чего к добавленному узлу применяется операция ВСПЛЫТИЕ для восстановления кучеобразного порядка.
Вставим в -кучу, изображенную на рис. 4.9, новый элемент с ключом .
Рис. 4.9.
Сначала добавляем к дереву новый узел с номером и приписываем ему элемент с ключом . Получим дерево, представленное на рис. 4.10.
Рис. 4.10.
Затем применяем к узлу операцию ВСПЛЫТИЕ. При описании этой операции использовался именно приведенный пример (см. рис. 4.3, 4.4, 4.5).
Вычислительная сложность данной операции равна константе плюс вычислительная сложность операции ВСПЛЫТИЕ, то есть .
Реализация операции ВСТАВКА
Операция УДАЛЕНИЕ.
Используется для удаления элемента, приписанного узлу с заданным номером . Сначала элемент, приписанный последнему узлу дерева, переносится на место удаляемого элемента, последний узел при этом становится ненужным и поэтому удаляется из дерева. Далее, если узел , в который помещен новый элемент, имеет родителя с большим ключом, то к узлу применяется операция ВСПЛЫТИЕ, в противном случае — ПОГРУЖЕНИЕ.
Таким образом, ориентируясь на худший случай, вычислительную сложность операции УДАЛЕНИЕ оцениваем величиной .
Реализация операции УДАЛЕНИЕ
Операция УДАЛЕНИЕ_МИНИМУМА. Эта операция предназначена для взятия из кучи элемента с минимальным ключом (он находится в корне дерева) и удаления его из кучи с помощью операции УДАЛЕНИЕ.
Реализация операции УДАЛЕНИЕ_МИНИМУМА
Функция MINKEY. Эта функция предназначена для определения минимального ключа без удаления соответствующего элемента.
Реализация функции MINKEY
Трудоемкость операции, очевидно, равна .
Операция УМЕНЬШЕНИЕ_КЛЮЧА. Предназначена для уменьшения ключа у элемента, приписанного узлу с заданным номером , на заданную величину .
Это действие может нарушить кучеобразный порядок лишь таким образом, что уменьшенный ключ элемента в узле станет меньше ключа элемента в родительском узле. Для восстановления порядка в куче используется операция ВСПЛЫТИЕ.
Вычислительная сложность данной операции определяется временем, затрачиваемым на уменьшение ключа (то есть константой), и временем выполнения операции ВСПЛЫТИЕ (то есть . В итоге вычислительная сложность операции УМЕНЬШИТЬ_КЛЮЧ равна .
Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА
Операция ОКУЧИВАНИЕ.
Заметим, что если -куча создается путем -кратного применения операции ВСТАВКА, то суммарная трудоемкость ее создания будет равна . Если же все элементов сначала занимают в произвольном порядке массив и, соответственно, массив , то можно превратить их в -кучу, применяя операцию ПОГРУЖЕНИЕ по очереди к узлам .
Такой процесс будем называть окучиванием массива. Для доказательства того, что в результате действительно устанавливается кучеобразный порядок, достаточно заметить, что если поддеревья с корнями в узлах упорядочены по правилу кучи, то после применения процедуры ПОГРУЖЕНИЕ к узлу поддерево с корнем в этом узле также станет упорядоченным по правилу кучи. Итак, остановимся на следующей реализации.
Реализация операции ОКУЧИВАНИЕ
Утверждение 3.
Вычислительная сложность операции ОКУЧИВАНИЕ равна .
Доказательство
Заметим, что трудоемкость погружения с высоты
равна , а количество узлов высоты
не превосходит . Осталось оценить сумму где , и убедиться, что полученная сумма есть .
Для суммирования можно воспользоваться формулой
Предоставляем читателю возможность завершить доказательство.
Операция СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ.
Эта операция применяется для получения списка элементов, которые имеют ключи, меньшие заданного значения , и реализуется следующим образом. Если ключ элемента, находящегося в корне, больше, чем , то это дерево не имеет искомых элементов. В противном случае включаем его в выходной список , а затем применяем ту же процедуру ко всем потомкам узла, включенного в список.
Пусть куча содержит элементов с ключами, меньшими, чем . По свойству кучи, они все расположены на ее "верхушке". Данная процедура обходит эту верхушку за время, пропорциональное , и для каждого из этих элементов просматривает все его (или меньше) непосредственных потомков. Получаем, что время выполнения данной процедуры является величиной .
Реализация операции СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ
Сводные данные о трудоемкости операций с d-кучами
| ВСПЛЫТИЕ | |
| ПОГРУЖЕНИЕ | |
| ВСТАВКА | |
| УДАЛЕНИЕ | |
| УДАЛЕНИЕ_МИН | |
| MINKEY | |
| УМЕНЬШЕНИЕ_КЛЮЧА | |
| ОБРАЗОВАTЬ_ОЧЕРЕДЬ | |
| СПИСОК_МИН |
Для -куч "неудобной" является операция слияния куч.
Основные определения
Приоритетная очередь — это абстрактный тип данных, предназначенный для представления взвешенных множеств. Множество называется взвешенным, если каждому его элементу однозначно соответствует число, называемое ключом или весом. Основными операциями над приоритетной очередью являются следующие операции:
ВСТАВИТЬ в множество новый элемент со своим ключом.НАЙТИ в множестве элемент с минимальным ключом. Если элементов с минимальным ключом несколько, то находится один из них. Найденный элемент не удаляется из множества.УДАЛИТЬ из множества элемент с минимальным ключом. Если элементов с минимальным ключом несколько, то удаляется один из них.
Дополнительные операции над приоритетными очередями:
ОБЪЕДИНИТЬ два множества в одно.УМЕНЬШИТЬ ключ указанного элемента множества на заданное положительное число.
Приоритетная очередь естественным образом используется в таких задачах, как сортировка элементов массива, поиск во взвешенном неориентированном графе минимального остовного дерева, поиск кратчайших путей от заданной вершины взвешенного графа до его остальных вершин, и во многих других.
Приоритетную очередь можно представить с помощью массива или списка элементов, но такие реализации неэффективны по времени выполнения основных операций. Так, например, поиск элемента с минимальным ключом в неупорядоченном массиве или списке требует последовательного просмотра всех его элементов. Если поддерживать упорядоченность массива или списка по ключу, то "неудобной" окажется операция вставки нового элемента.
Чаще всего приоритетная очередь представляется с помощью корневого дерева или набора корневых деревьев с определенными свойствами. При этом узлам дерева ставятся во взаимно однозначное соответствие элементы рассматриваемого множества.
Соответствие между узлами дерева и элементами множества называется кучеобразным, если для каждого узла соблюдается следующее условие:
Ключ элемента, приписанного узлу , не превосходит ключей, приписанных его потомкам.
Такие представления взвешенных множеств называются кучами. Вид дерева и способ его представления в памяти компьютера подбирается в зависимости от тех операций, которые предполагается выполнять над множеством, и от того, насколько эти операции сказываются на суммарной трудоемкости алгоритма.
Представление приоритетной очереди с помощью d-кучи
Представление приоритетной очереди с помощью -кучи основано на использовании так называемых завершенных -арных деревьев ().
Завершенное -арное дерево — это корневое дерево со следующими свойствами:
- Каждый внутренний узел (то есть узел, не являющийся листом дерева), за исключением, быть может, только одного, имеет ровно
потомков. Один узел-исключение может иметь от до
потомков.Если — глубина дерева, то для любого
такое дерево имеет ровно узлов глубины .Количество узлов глубины в дереве глубины
может варьироваться от до . Это свойство является следствием первых двух.
Узлы завершенного -арного дерева принято нумеровать следующим образом: корень получает номер 0, потомки узла с номером
получают номера: , , , . Такая нумерация удобна тем, что позволяет разместить узлы дерева в массиве в порядке возрастания их номеров, при этом позиции потомков любого узла в массиве легко вычисляются по позиции самого узла. Так же легко по позиции узла вычислить позицию его родителя. Так, для узла, расположенного в позиции , родительский узел располагается в позиции , где — операция деления нацело.
В изображении завершенного -арного дерева узлы одинаковой глубины удобно располагать на одном уровне, при этом потомки одного узла располагаются слева направо в порядке объявленных номеров. При таком рисовании нижний уровень заполняется, возможно, не полностью.
Отметим некоторые простые утверждения о завершенных -арных деревьях, которые будут полезны при анализе трудоемкости основных операций.
Утверждение 1.
Длина пути из корня завершенного -арного дерева с узлами в любой лист удовлетворяет неравенствам:
Доказательство
Минимальное количество узлов в -куче высоты
(), по свойствам 2 и 3 -арного дерева, очевидно, равно
(последний уровень содержит лишь один узел).
Максимальное количество узлов в такой -куче равно (последний уровень содержит узлов). Отсюда имеем неравенства:
Суммируя левую и правую части как геометрические прогрессии, получим
и после некоторых очевидных оценок с помощью логарифмирования получаем требуемые неравенства:
Утверждение 2.
Количество узлов высоты не превосходит .
Под высотой узла понимается расстояние от него до наиболее далекого потомка. Кучу, содержащую элементов, будем представлять двумя массивами — и , — полагая что — имя элемента, приписанного узлу ; — его ключ. Иногда под
удобно понимать сам элемент исходного множества или ссылку на него. В некоторых прикладных задачах нет необходимости помещать в приоритетную очередь ни сами элементы, ни их имена, в таких случаях при организации кучи используется лишь массив .
На рис. 4.1 приведен пример кучи для , . Кружочками изображены узлы дерева, в них записаны элементы массива, представляющие имена элементов кучи.
Пример кучи при , для приоритетной очереди, содержащей элементы с ключами , изображен на рис. 4.2, где пара чисел в каждом кружочке обозначает номер узла и ключ соответствующего элемента.
Рис. 4.1.
Рис. 4.2.
Применение приоритетных очередей в задаче сортировки
Под задачей сортировки в простейшем случае понимают следующее: дана последовательность
из элементов некоторого линейно упорядоченного множества, например целых или вещественных чисел, записанных в массив . Требуется переставить элементы массива так, чтобы после перестановки выполнялись неравенства:
Уточнения этой задачи связаны с теми средствами, с помощью которых предполагается ее решение. Нас интересуют алгоритмы с точки зрения их компьютерной реализации. Оценивая качество различных алгоритмов, обычно интересуются тем, как зависит время счета от длины сортируемой последовательности и требуется ли для этого дополнительная память, размер которой определяется параметром . Существенную роль при этом играет метод доступа к элементам памяти. При сортировке во внутренней (оперативной) памяти обычно используется прямой доступ, а во внешней — последовательный.
Сортировка методом "разделяй и властвуй".
Предположим, что в нашем распоряжении имеется процедура РАЗДЕЛЯЙ , которая по заданным значениям индексов , находит некоторое промежуточное значение и переставляет элементы сегмента так, чтобы для
выполнялось неравенство , а для — неравенство .
Тогда для сортировки сегмента
может быть использована рекурсивная процедура СОРТИРУЙ.
Для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ .
Заметим, что если бы процедура РАЗДЕЛЯЙ работала линейное от длины сегмента время и давала значение , близкое к середине между
и , то число обращений к ней приблизительно равнялось бы и сортировка всего массива проходила бы за время порядка . Однако можно доказать, что при естественной реализации эта оценка справедлива лишь в среднем.
Упражнения
- Разработайте вариант процедуры СОРТИРУЙ без использования рекурсии. Сколько дополнительной памяти требуется для запоминания границ еще не отсортированных сегментов?Охарактеризуйте работу процедуры СОРТИРУЙ на заранее отсортированном массиве.Напишите на известном вам алгоритмическом языке программу сортировки числового массива с помощью процедуры СОРТИРУЙ и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел.Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?
Сортировка с помощью d-кучи.
Для представления сортируемой последовательности используем структуру -кучи. Сортировку можно провести в два этапа.
- Окучить сортируемый массив, применяя последовательно операцию ПОГРУЖЕНИЕ по очереди к узлам
в предположении, что сначала все ключей занимают в произвольном порядке массив .Осуществить окончательную сортировку следующим образом. Первый (минимальный) элемент кучи меняем местами с последним, уменьшаем размер кучи на 1 (минимальный элемент остается в последней позиции массива , не являясь уже элементом кучи) и применяем операцию ПОГРУЖЕНИЕ к корню, затем повторяем аналогичные действия, пока размер кучи не станет равным 1.
Эти два этапа реализуются с помощью процедуры SORT, которая сортирует массив по убыванию ключей:
Заметим, что процедура не требует дополнительной памяти, размер которой зависел бы от длины массива .
Упражнения
- Докажите, что оператор
в процедуре можно заменить оператором
Напишите программу сортировки числового массива с помощью процедуры и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел. Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?
Сортировка "слиянием".
Этот метод является разновидностью метода "разделяй и властвуй"; впрочем, уместнее было бы назвать его "властвуй и объединяй".
Предположим, что у нас есть процедура СЛИВАЙ (, которая два уже отсортированных сегмента и
преобразует (сливает) в один сегмент , делая его полностью отсортированным. Тогда рекурсивная процедура
очевидно, сортирует сегмент , а для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ . Как видим, вопрос балансировки размера сегментов решается здесь просто. Число обращений к процедуре СЛИВАЙ
равно , а время ее выполнения легко сделать линейным от суммарной длины сливаемых сегментов.
Упражнения
- Разработайте процедуру СЛИВАЙ и вариант процедуры СОРТИРУЙ без использования рекурсии. Сколько дополнительной памяти требуется для ее реализации?Оцените теоретически время работы алгоритма по методу слияния.Напишите на известном вам алгоритмическом языке программу сортировки числового массива методом слияния и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел.Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?
Левосторонние кучи
Левосторонняя куча — это представление приоритетной очереди с помощью так называемого левостороннего бинарного дерева. При реализации приоритетных очередей левосторонними кучами предусматривается возможность их объединения.
Бинарным деревом называется корневое дерево, у которого каждый узел имеет не более двух непосредственных потомков. Один из потомков называется левым, другой, если он есть, — правым. Узел называется неполным, если он имеет менее двух непосредственных потомков. В частности, листья дерева являются неполными узлами.
Рангом узла будем называть увеличенное на 1 расстояние (число ребер) от него до ближайшего неполного потомка.
Ранг узла также можно определить следующим образом. Расширить данное дерево до полного бинарного дерева, добавляя к каждому узлу, имеющему менее двух потомков, в том числе и к листьям исходного дерева, недостающее количество потомков. Затем приписать каждому из листьев полученного расширенного дерева ранг 0, а ранг каждого из остальных узлов определить как минимум из рангов его непосредственных потомков плюс 1. Очевидно, что ранги вершин исходного дерева совпадут с рангами соответствующих вершин расширенного дерева.
Левостороннее дерево — это бинарное дерево, для каждого узла которого ранг его левого непосредственного потомка в расширенном дереве не меньше ранга его правого потомка.
Ветвью бинарного дерева мы называем последовательность его узлов, начинающуюся с корня и заканчивающуюся листом, такую, что каждый следующий узел является непосредственным потомком предыдущего.
Правой ветвью дерева мы называем ветвь, заканчивающуюся в узле, не имеющем правого потомка, такую, что каждый следующий узел является непосредственным правым потомком предыдущего.
Пример левостороннего дерева (и его расширения) приведен на рис. 5.1. Ребра исходного дерева выделены жирными линиями, а ребра, добавленные при расширении, — пунктиром. Числа рядом с узлами — их ранги.
Рис. 5.1.
Операции с левосторонними кучами
Операция СЛИЯНИЕ. Эта операция позволяет слить две левосторонние кучи и в одну кучу . Реализуется она посредством слияния правых путей двух исходных куч в один правый путь, упорядоченный по правилам кучи, а левые поддеревья узлов сливаемых правых путей остаются левыми поддеревьями соответствующих узлов в результирующем пути. В полученной куче необходимо восстановить свойство левизны каждого узла. Это свойство может быть нарушено только у узлов правого пути полученной кучи, так как левые поддеревья с корнями в узлах правых путей исходных куч не изменились. Восстанавливается свойство левизны при помощи прохода правого пути снизу вверх (от листа к корню) с попутным транспонированием в случае необходимости левых и правых поддеревьев и вычислением новых рангов проходимых узлов.
Рассмотрим процесс слияния двух левосторонних куч
и , изображенных на рис. 5.2.
Рис. 5.2.
Числа внутри кружочков являются ключами элементов, приписанных к соответствующим узлам. Правые ветви куч показаны жирными линиями. Числа рядом с узлами — их ранги.
После объединения правых путей получим дерево, изображенное на рис. 5.3. Оно не является левосторонним. В скобках указаны ранги узлов, какими они были в исходных кучах до слияния.
Восстановление свойства левизны кучи начинаем с последнего узла правой ветви. Это узел с ключом . Очевидно, он должен иметь ранг , совпадающий с его старым значением и поэтому не требующий обновления.
Рис. 5.3.
Следующий по направлению к корню узел правой ветви имеет ключ , ранг его левого сына не меньше ранга правого сына, следовательно, условие левизны выполняется и поэтому транспонирования его левого и правого поддеревьев не требуется. Однако ранг этого узла необходимо обновить, так как его старое значение не совпадает с увеличенным на
минимальным из рангов его потомков, то есть с числом 2. Обновив ранг, получим кучу, изображенную на рис. 5.4.
Рис. 5.4.
Теперь рассмотрим узел с ключом . Он имеет левого сына с ключом
и рангом и правого сына с ключом и рангом . Для восстановления свойства левизны в этом узле необходимо поменять местами его левое и правое поддеревья и обновить ранг. Его новым значением будет минимум из рангов его потомков (это ранг нового правого сына) плюс , то есть . В результате получаем дерево, изображенное на рис. 5.5.
Рис. 5.5.
Сводные данные о трудоемкости операций с левосторонними кучами
| СЛИТЬ | |
| ВСТАВИТЬ | |
| УДАЛИТЬ_МИН | |
| МИН | |
| УДАЛИТЬ | |
| УМЕНЬШИТЬ_КЛЮЧ | |
| ОБРАЗОВАТЬ_ОЧЕРЕДЬ |
Свойства левостороннего дерева
- Правая ветвь из любого узла дерева имеет минимальную длину среди всех ветвей, исходящих из этого узла.Длина правой ветви левостороннего дерева, имеющего узлов, ограничена величиной , .
Первое свойство непосредственно следует из определения левостороннего дерева. Для доказательства второго свойства рассмотрим левостороннее дерево , у которого длина правой ветви равна . Индукцией по числу докажем, что число узлов в таком дереве удовлетворяет неравенству . Действительно, при утверждение очевидно. При левое и правое поддеревья дерева будут левосторонними, а ранги их корней больше или равны . Следовательно, по предположению индукции число узлов в каждом из них больше или равно , а в дереве — больше или равно
Для реализации приоритетной очереди с помощью левосторонней кучи будем использовать узлы вида
содержащие следующую информацию:
element — элемент приоритетной очереди или ссылка на него (используется прикладной программой);key — его ключ (вес);rank — ранг узла, которому приписан рассматриваемый элемент;left, right — указатели на левое и правое поддеревья;parent — указатель на родителя.Куча представляется указателем на ее корень. Если — указатель на корень кучи, то через будем обозначать и саму кучу. Заметим, что указатель на родителя используется лишь в операциях УДАЛИТЬ и УМЕНЬШИТЬ_КЛЮЧ (см. ниже).
Ленивая левосторонняя куча
Ленивая левосторонняя куча — это представление приоритетной очереди левосторонним деревом, но при этом, в отличие от обычной левосторонней кучи, каждый узел может содержать, а может и не содержать в себе (быть пустым) элемент приоритетной очереди. Для реализации ленивой левосторонней кучи к каждому узлу добавляется еще одно поле, для хранения признака, содержит ли данный узел элемент или является пустым. Такие кучи носят название "ленивых" из-за способа выполнения операций УДАЛИТЬ и СЛИТЬ.
При выполнении операции УДАЛИТЬ узел не удаляется, а лишь помечается как пустой. Время "ленивого" выполнения этой операции равно .
Операция СЛИТЬ осуществляется следующим образом. Заводится пустой корневой узел, сыновьями которого становятся корневые узлы объединяемых куч. Время "ленивого" выполнения этой операций равно .
При операции НАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ происходит расплата за "лень", так как эта операция выполняется следующим образом. Сначала делается обход дерева сверху для составления списка, содержащего верхние непустые узлы, чьи родители помечены как пустые. Затем из построенного списка образуется приоритетная очередь с непустыми узлами, после чего берется элемент, содержащийся в корне дерева. Справедливо следующее
Утверждение.
Время выполнения операции НАЙТИ_ЭЛЕМЕНТ_С МИНИМАЛЬНЫМ_КЛЮЧОМ является величиной
где — количество верхних пустых элементов.
При операции УДАЛИТЬ_ЭЛЕМЕНТ_МИНИМАЛЬНЫМ_КЛЮЧОМ также происходит расплата за "лень". Она выполняется следующим образом. Сначала, как описано выше, делается обход дерева сверху для нахождения узла с минимальным ключом; найденный узел помечается как пустой. После этого, снова путем обхода дерева сверху, составляется список верхних непустых узлов. И, наконец, поддеревья с корнями в этих узлах сливаются в одну кучу .
Операция ВСТАВИТЬновый элемент в кучу
производится посредством слияния кучи с кучей, содержащей единственный элемент .
Операция ОБРАЗОВАТЬ_ОЧЕРЕДЬ в форме ленивой левосторонней кучи из элементов списка производится как в обычных левосторонних кучах, то есть с неленивыми слияниями.
Операция УМЕНЬШИТЬ_КЛЮЧ элемента на величину выполняется следующим образом. Ключ элемента уменьшается на , узел, его содержащий, помечается как пустой, из этого элемента
образуется новая одноэлементная куча, которая сливается с исходной кучей.
Самоорганизующаяся куча
Самоорганизующаяся куча — это представление приоритетной очереди корневым деревом, операции с которым производятся аналогично операциям с левосторонней кучей, но без использования рангов. Длина правого пути из корня такого дерева в лист может быть произвольной, поэтому время выполнения всех операций в худшем случае есть , где — число элементов в очереди. Однако среднее время выполнения произвольных операций есть , то есть время, приходящееся на одну операцию, как ни удивительно, является величиной . Для их реализации необходимо с каждым узлом дерева хранить элемент, его ключ, указатели на левое и правое поддеревья, то есть узлы представлять записями вида
Операция СЛИТЬ кучи и в одну кучу
выполняется следующим образом. Правые пути двух исходных куч
и сливаются в один путь, упорядоченный по правилам кучи, и этот путь становится левым путем результирующей кучи . Левые поддеревья узлов, попавших в результирующий левый путь, становятся правыми.
Операция ВСТАВИТЬ в кучу новый элемент производится посредством слияния кучи с кучей, содержащей единственный элемент . Таким образом, время выполнения этой операции равно времени выполнения операции СЛИТЬ.
Операция УДАЛИТЬ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ производится посредством удаления корня кучи и слияния его левой и правой подкуч. Таким образом, вычислительная сложность этой операции равна вычислительной сложности операции СЛИТЬ.
ОперацияНАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ выполняется, очевидно, за время , так как этот элемент находится в корне.
Анализ времени выполнения операции СЛИТЬ. Поскольку время выполнения всех трудоемких операций определяется временем выполнения операции СЛИТЬ, остается проанализировать именно эту операцию. Очевидно, время ее выполнения пропорционально количеству узлов в правых путях исходных куч и . Длина такого пути в худшем случае может зависеть линейно от количества узлов в соответствующей куче. Таким образом, время выполнения операции СЛИТЬ есть величина , где , , — количества узлов в кучах , , , соответственно.
Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.
Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть — потенциал коллекции после выполнения -й операции.
Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.
Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть — потенциал коллекции после выполнения -й операции.
Утверждение.
Время выполнения операций СЛИТЬ, примененных к коллекции, состоящей из куч с нулевым потенциалом, является величиной , где
— общее количество узлов в коллекции.
Доказательство.
Пусть -я операция заключается в слиянии куч и в результирующую кучу . Пусть перед ее выполнением и — количества тяжелых узлов в правых путях куч и соответственно,
и — количества легких узлов в этих путях, ,
— количества тяжелых узлов в остальных частях куч.
Время выполнения этой операции с точностью до постоянного множителя оценивается сверху величиной .
Подсчитаем изменение потенциала при ее выполнении. Имеем
По завершении этой операции тяжелые узлы правых путей становятся легкими, их количество равно . Легкие узлы правых путей могут как стать тяжелыми, так и остаться легкими, их будет не более штук, а количества тяжелых узлов в остальной части обоих деревьев не изменились. Следовательно, количество
тяжелых узлов после выполнения операции удовлетворяет неравенству
Таким образом, получаем изменение потенциала
и, следовательно,
Из определения легкого узла следует, что количество легких узлов в куче не превосходит логарифма количества узлов в этой куче.
Следовательно, где , а — общее количество узлов в исходных кучах.
Суммируя левую и правую части последнего неравенства по , получаем, что величина
с точностью до постоянного множителя оценивается сверху величиной, пропорциональной , то есть принадлежит .
Величина является амортизационной оценкой времени выполнения операции СЛИТЬ, то есть величиной .
Замечание.
Вначале коллекция, состоящая из куч, к которым применяются операций СЛИТЬ, может иметь произвольное количество узлов, в сумме равное .Важно, чтобы потенциал каждой из них, следовательно, и суммарный потенциал был равен нулю, то есть кучи не должны первоначально иметь тяжелых узлов.
Это могут быть, например, кучи, целиком являющиеся левыми путями. Крайний случай — это куча высоты с минимальным количеством узлов, не имеющая тяжелых узлов, а также это могут быть кучи с заполненным последним уровнем узлов. Другой крайний случай — это куча высоты
с максимальным количеством узлов, не имеющая тяжелых узлов. Остальные варианты являются промежуточными.
Особое значение имеет случай, когда каждая из начальных куч состоит из единственного узла.
Итак, для всех коллекций таких куч амортизационное время выполнения одной операции СЛИТЬ является величиной , где
— общее количество их узлов.
Сводные данные о трудоемкости операций с самоорганизующимися кучами
| СЛИТЬ | ||
| ВСТАВИТЬ | ||
| УДАЛИТЬ_МИНИМУМ | ||
| НАЙТИ_МИНИМУМ |
Сводные данные о трудоемкости операций с ленивыми левосторонними кучами
| УДАЛИТЬ УЗЕЛ | |
| НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ | |
| УДАЛИТЬ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ | |
| СЛИТЬ | |
| ВСТАВИТЬ | |
| ОБРАЗОВАТЬ ОЧЕРЕДЬ | |
| УМЕНЬШИТЬ КЛЮЧ |
Биномиальные кучи
Для каждого биномиальное дерево определяется следующим образом: — дерево, состоящее из одного узла высоты ; далее при
дерево
высоты формируется из двух деревьев , при этом корень одного из них становится потомком корня другого. На рис. 7.1
изображены биномиальные деревья .
Биномиальный лес — это набор биномиальных деревьев, в котором любые два дерева имеют разные высоты.
Рис. 7.1.
Фибоначчиевы кучи
Название рассматриваемых куч связано с использованием чисел Фибоначчи при анализе трудоемкости выполнения операций. В отличие от биномиальных куч, в которых операции вставки, поиска элемента с минимальным ключом, удаления, уменьшения ключа и слияния выполняются за время , в фибоначчиевых кучах они выполняются более эффективно. Операции, не требующие удаления элементов, в этих кучах имеют учетную стоимость . Теоретически фибоначчиевы кучи особенно полезны, если число операций удаления мало по сравнению с остальными операциями. Такая ситуация возникает во многих приложениях.
Например, алгоритм, обрабатывающий граф, может вызывать процедуру уменьшения ключа для каждого ребра графа. Для плотных графов, имеющих много ребер, переход от к в оценке времени работы этой операции может привести к заметному уменьшению общего времени работы. Наиболее быстрые известные алгоритмы для задач построения минимального остовного дерева или поиска кратчайших путей из одной вершины используют фибоначчиевы кучи.
К сожалению, скрытые константы в асимптотических оценках трудоемкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (-ичные) кучи на практике эффективнее. С практической точки зрения желательно придумать структуру данных с теми же асимптотическими оценками, но с меньшими константами. Такие кучи будут рассмотрены в следующих разделах.
При отсутствии операций уменьшения ключа и удаления элемента фибоначчиевы кучи имели бы ту же структуру, что и биномиальные. Но в общем случае фибоначчиевы деревья обладают большей гибкостью, чем биномиальные. Из них можно удалять некоторые узлы, откладывая перестройку дерева до удобного случая.
Строение фибоначчиевой кучи. Каждая фибоначчиева куча состоит из нескольких деревьев. В отличие от биномиальных деревьев, здесь дети любого узла могут записываться в любом порядке. Они связываются в двусторонний циклический список. Каждый узел этого списка имеет поля и , указывающие на его соседей в списке. На рис. 7.2 показано схематическое строение фибоначчиевой кучи.
Рис. 7.2.
Двусторонние циклические списки удобны по двум причинам. Во-первых, из такого списка можно удалить любой узел за время . Во-вторых, два таких списка можно соединить в один за время .
Помимо указанной информации, каждый узел имеет поле , где хранится его степень (число детей), а также поле . В этом поле хранится булевское значение. Смысл его таков:
истинно, если узел потерял ребенка после того, как он в последний раз сделался чьим-либо потомком. Позже будет ясно, как и когда это поле используется.
Корни деревьев, составляющих фибоначчиеву кучу, также связаны с помощью указателей и в двусторонний циклический список, называемый корневым списком. Таким образом, каждый узел фибоначчиевой кучи представляется записью вида
Доступ к куче производится ссылкой
на узел с минимальным ключом. Кроме того, общее число узлов задается атрибутом .
Потенциал. При анализе учетной стоимости операций используют метод потенциала. Пусть — число деревьев в корневом списке кучи , а — количество помеченных узлов. Потенциал определяется формулой
В каждый момент времени в памяти может храниться несколько куч; общий потенциал по определению равен сумме потенциалов всех этих куч. В дальнейшем мы выберем единицу измерения потенциала так, чтобы единичного изменения потенциала хватало для оплаты операций (формально говоря, мы умножим потенциал на подходящую константу). В начальном состоянии нет ни одной кучи и потенциал равен . Как и положено, потенциал всегда неотрицателен.
Максимальная степень Через обозначим верхнюю границу для степеней узлов в кучах, которые могут появиться при выполнении операций. Аргументом функции является общее число всех узлов в куче, обозначаемое через .
Мы не будем углубляться в анализ трудоемкости операций с фибоначчиевыми кучами, отсылая читателя к соответствующей литературе [7], [19]
скажем только, что и все операции, кроме операции удаления элемента, имеют амортизационную трудоемкость , а операция удаления — .
Фибоначчиевы кучи ввел М.Фредман и Р.Тарьян [17].В их статье описаны также приложения фибоначчиевых куч к задачам о кратчайших путях из одной вершины, о кратчайших путях для всех пар вершин, о паросочетаниях с весами и о минимальном покрывающем дереве.
Впоследствии Д.Дрисколл и Р.Тарьян [16]
разработали структуру данных, называемую , как замену для фибоначчиевых куч. Есть две разновидности такой структуры данных. Одна из них дает те же оценки учетной стоимости, что и фибоначчиевы кучи. Другая — позволяет выполнять операцию за время в худшем случае, а операции и Delete — за время
в худшем случае. Эта структура данных имеет также некоторые преимущества по сравнению с фибоначчиевыми кучами при использовании в параллельных алгоритмах.
Свойства биномиальных деревьев
Дерево состоит из корня с присоединенными к нему корнями поддеревьев в указанном порядке.Дерево имеет высоту .Дерево имеет ровно узлов.В дереве на глубине имеется ровно узлов.В дереве корень имеет степень , остальные узлы имеют меньшую степень.Для каждого натурального числа n существует биномиальный лес, в котором количество узлов равно .Максимальная степень вершины в биномиальном лесе с
узлами равна .Биномиальный лес содержит не более
биномиальных поддеревьев.
Чтобы убедиться в существовании биномиального леса из узлов, представим в двоичной системе счисления (разложим по степеням двойки) , где . Для каждого , такого, что , в искомый лес включаем дерево .
Биномиальная куча — это набор биномиальных деревьев, узлам которых приписаны элементы взвешенного множества в соответствии с кучеобразным порядком, при котором вес элемента, приписанного узлу, не превосходит весов элементов, приписанных его потомкам.
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей
где — ключ (вес) элемента, приписанного узлу, — родитель узла,
— левый ребенок узла, — правый брат узла, — степень узла.
Доступ к куче осуществляется ссылкой на самое левое поддерево. Корни деревьев, из которых составлена куча, оказываются организованными с помощью поля в так называемый корневой односвязный список.
Поиск элемента с минимальным ключом. Поскольку искомый элемент находится в корне одного из деревьев кучи, элемент с минимальным ключом находится путем просмотра корневого списка за время .
Слияние двух очередей. Две очереди и объединяются в одну очередь следующим образом. Последовательно выбираются деревья из исходных очередей в порядке возрастания их высот и вставляются в результирующую очередь , вначале пустую.
Если дерево очередной высоты присутствует лишь в одной из исходных очередей, то перемещаем его в результирующую очередь. Если оно присутствует в одной из исходных очередей и уже есть в результирующей очереди, то объединяем эти деревья в одно , которое вставляем в . Если присутствует во всех трех очередях, то сливаем два из них в
и вставляем в , а третье дерево просто перемещаем в . Трудоемкость — .
Вставка нового элемента. Создается одноэлементная очередь из вставляемого элемента, которая объединяется с исходной очередью. Трудоемкость — .
Удаление минимального элемента. Сначала в исходной куче
производится поиск дерева , имеющего корень с минимальным ключом. Найденное дерево удаляется из , его прикорневые поддеревья включаются в новую очередь , которая объединяется с исходной очередью . Трудоемкость — .
Уменьшение ключа. Осуществляется с помощью всплытия. Трудоемкость — .
Удаление элемента. Уменьшается ключ удаляемого элемента до , применяется всплытие, всплывший элемент удаляется как минимальный. Трудоемкость — .
Основные определения
Рассматриваемые здесь тонкие и, в следующей лекции, толстые кучи предложены М.Фредманом и Х.Капланом как альтернатива фибоначчиевым кучам. Долгое время фибоначчиевы кучи считались рекордными по производительности. Оценки операций над фибоначчиевыми кучами имеют амортизационный характер, а скрытые в них константы велики настолько, что реальный выигрыш во времени работы с ними достигался только на данных "астрономических" размеров. Рассматриваемые здесь тонкие кучи имеют те же асимптотические оценки, что и фибоначчиевы, но гораздо практичнее их. Оценки для толстых куч "хуже" по операции слияния, выполняемой за O(\log n) времени. Достоинством этой структуры является то, что ее оценки рассчитаны на худший случай. Заметим, что на данный момент ни фибоначчиевы, ни толстые, ни тонкие кучи не являются рекордными, так как Г.Бродал предложил новую структуру, которую мы будем называть кучей Бродала. Кучи Бродала характеризуется такими же, как и фибоначчиевы кучи, оценками операций, но все оценки справедливы для худшего случая. К сожалению, структура, предложенная Г.Бродалом, сложна для реализации. Рассмотрим реализацию приоритетной очереди с помощью тонкой кучи.
Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.
Тонкое дерево
ранга — это дерево, которое может быть получено из биномиального дерева
удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына. Заметим, что у листьев детей нет, а если у корня удалить самого левого сына, то
превратится в . Ранг тонкого дерева равен количеству детей корня.
Для любого узла в дереве обозначим: — количество детей узла ; — ранг соответствующего узла в биномиальном дереве .
Тонкое дерево удовлетворяет следующим условиям:
- Для любого узла либо , в этом случае говорим, что узел не помечен (полный); либо , в этом случае говорим, что узел помечен (неполный).Корень не помечен (полный).Для любого узла ранги его детей от самого правого к самому левому равны соответственно .Узел помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.
На рис. 8. 1 приведены примеры тонких деревьев; числа рядом с узлами обозначают их ранги. Вверху изображено биномиальное дерево , внизу — два полученных из тонких дерева ранга три. Стрелки указывают на помеченные узлы. Заметим, что биномиальное дерево является тонким деревом, у которого все узлы не помечены.
Тонкий лес — это набор тонких деревьев, ранги которых не обязательно попарно различны.
Рис. 8.1.
Тонкая куча — это кучеобразно нагруженный тонкий лес.
Заметим, что в тонкой куче могут встречаться тонкие деревья одинакового ранга, в то время как в биномиальной куче все деревья должны иметь попарно различные ранги.
Утверждение. Для любого натурального числа существует тонкий лес, который содержит ровно элементов и состоит из тонких деревьев попарно различных рангов.
Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.
Пусть — максимально возможный ранг узла в тонкой куче, содержащей элементов.
Теорема [22]
В тонкой куче из элементов , где — золотое сечение.
Доказательство. Сначала покажем, что узел ранга
в тонком дереве имеет не менее потомков, включая самого себя, где — -е число Фибоначчи, определяемое соотношениями , , для .
Действительно, пусть — минимально возможное число узлов, включая самого себя, в тонком дереве ранга . По свойствам и
тонкого дерева получаем следующие соотношения:
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что для любых . Неравенство
хорошо известно.
Теперь убедимся в том, что максимально возможный ранг
тонкого дерева в тонкой куче, содержащей элементов, не превосходит числа . Действительно, выберем в тонкой куче дерево максимального ранга. Пусть — количество вершин в этом дереве, тогда .
Отсюда следует, что .
Представление тонкой кучи в памяти компьютера.
Тонкие кучи формируют из узлов, представленных записями следующего вида:
где — ключ элемента, приписанного узлу; — указатель на ближайшего левого брата, если такового нет, то на родителя, а если нет и родителя, то указатель заземлен; — указатель на ближайшего правого брата, если такового нет, то указатель заземлен; — указатель на самого левого сына, если такового нет, то указатель заземлен; — ранг узла.
Таким образом, узлы-братья связаны в двусвязный список при помощи указателей и . У самого левого брата в этом списке указатель указывает на общего родителя всех узлов в списке. У самого правого брата из списка указатель заземлен. Корни деревьев в тонкой куче связаны в односвязный циклический список. Этот список будем называть корневым списком. Корневой список реализуется при помощи поля . Поле у каждого узла корневого списка заземлено.
В случае необходимости в описании узла может присутствовать и другая прикладная информация. На рис. 8.2 приведен пример тонкой кучи.
Тонкая куча
Представление кучи со ссылками, в узлах указаны ранги
Рис. 8.2.
Заметим, что принадлежность заданного узла корневому списку кучи осуществляется проверкой указателя на заземленность.
Введем еще одну запись , которая будет соответствовать отдельной куче и иметь вид
где — указатель на начальный элемент корневого списка; — указатель на элемент корневого списка с минимальным ключом.
Очевидно, что узел с минимальным ключом обязательно находится в корневом списке.
Реализация основных операций и оценки трудоемкости
Сосредоточим внимание на амортизационных оценках трудоемкости. Будем получать их методом потенциалов. Потенциалом тонкой кучи будем считать величину , где — количество деревьев в куче, а — число помеченных вершин. Заметим, что потенциал кучи неотрицателен и в начальный момент равен .
Операция MakeHeap. Эта операция создает указатель на новую пустую кучу. Очевидно, фактическая стоимость операции есть , а потенциал созданной кучи равен .
Операция FindMin (H). Указатель на узел с минимальным ключом в куче определяется с помощью указателя . Если куча пуста, то результирующий указатель нулевой. Амортизационная оценка совпадает с фактической и равна , потенциал не изменяется.
Операция Insert(i,H). С помощью этой операции осуществляется вставка в кучу нового элемента с ключом . При ее реализации создается новое тонкое дерево ранга , которое вставляется в корневой список кучи , разрывая его в произвольном месте. При необходимости перевычисляется ссылка на минимальный элемент.
Операция увеличивает потенциал на , так как добавляется одно дерево в корневой список кучи, но это не влияет на амортизационную оценку, которая равна фактической .
Операция Meld(H1, H2). Результатом этой операции является указатель на кучу, полученную слиянием двух куч
и . Она осуществляется соединением корневых списков сливаемых куч. При таком способе выполнения операции, как и при реализации вставки элемента в кучу, можем получить в корневом списке результирующей кучи несколько деревьев одинакового ранга. При удобном случае, а именно при удалении минимального элемента, мы освободим корневой список от этой неоднозначности. Оценка совпадает с оценками для всех предыдущих операций. Суммарный потенциал не изменяется.
Избыточное представление чисел
Рассматриваемое в этой лекции представление приоритетной очереди основано на использовании так называемых избыточных счетчиков, позволяющих за время O(1) инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь один из способов реализации толстых куч. На самом деле, для их реализации подойдет произвольный d-арный счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.
Основные определения. Избыточным -арным представлением неотрицательного целого числа будем считать последовательность , , такую, что
где , . Будем называть цифрой, стоящей в -м разряде. В примерах запятые между цифрами опускаем.
Заметим, что избыточное представление отличается от обычного -арного представления использованием "лишней" цифры , что приводит к неоднозначности представления чисел. Например, при число может быть представлено как и как .
В примерах, в которых , "цифру" 10 будем обозначать символом .
Назовем -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными , найдется цифра, отличная от .
Пример.
Пусть , а число представляется в обычной десятичной системе последовательностью , тогда представления и не являются регулярными -арными избыточными представлениями числа , а представления и регулярны.
Пусть — номер разряда, отличного от и ближайшего слева от -го разряда в регулярном -арном избыточном представлении .
Определим следующим образом: , если ,
и ; — произвольное число , если
и ; — не определено, если .
Величину будем называть прямым указателем. Пусть — -арное регулярное представление некоторого числа.
Фиксацией цифры b, стоящей в i-м разряде представления d,
назовем операцию, заключающуюся в обнулении цифры
и инкрементировании цифры , при этом если , то полагаем . При каждом выполнении операции фиксации будем обновлять значение . Очевидно, при операцию можно выполнить с помощью следующих операторов.
Инкрементирование i-й цифры избыточного представления d можно выполнить с помощью операторов
Очевидно, что инкрементирование -го разряда регулярного -арного избыточного представления числа
производит представление числа .
Нетрудно доказать, что операции фиксации и инкрементирования, примененные к регулярному избыточному представлению, не нарушают регулярности и корректно вычисляют указатели с трудоемкостью .
Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения . Оставляем детали в качестве упражнения.
Основные операции
Операция make-heap заключается в инициализации счетчиков. Трудоемкость .
Операция FindMinвозвращает указатель на минимальный элемент. Трудоемкость .
Операция Insert(key). Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
Операция уменьшения ключа DecreaseKey. Чтобы выполнить эту операцию, поступим следующим образом. Пусть— узел, на который указывает указатель . Вычитаемиз ключа узла . Если новый ключ меньше минимального ключа кучи , обмениваем ключ элементас ключом минимального элемента. Новых нарушений операция не создаст. Пусть — ранг. Если — нарушаемый узел, добавляемкак новое-ранговое нарушение инкрементированием-й цифрысчетчика нарушений. Трудоемкость .
Операция DeleteMin выполняется следующим образом. Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом. Трудоемкость операции равна .
Операция удаления элемента. Выполняется с помощьюи затем. Трудоемкость операции .
Операция Meld(h1, h2). Выполняется следующим образом. Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча —. Пройти по счетчику нарушений от младшей цифры к старшей, пропуская цифры со значением .
Для - й цифрыделаем операцию фиксирования на каждой цифре, показываемой прямым указателем, если эта цифра имеет значение 2. Затем, если, фиксируем . Если, преобразуем это-ранговое нарушение в -ранговое нарушение, как при фиксировании, используя-рангового брата нарушенного узла вместо (несуществующего) другого-рангового нарушения.
Как тольконе будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчикав корневой счетчикинкрементированием соответствующих цифр. Если минимальный узел содержит меньший ключ, чем минимальный узел, следует установить новым минимальным узлом минимальный узел . Затем нужно вернуть модифицированную кучув качестве результата. Трудоемкость операции равна .
Операция DeleteViolation. Для освобождения кучи от нарушений достаточно выполнить операторы
Основываясь на описанной выше реализации толстой кучи, получаем следующий результат. В толстых кучах операцииивыполняются за время , а и— за время .
Замечание.
Существует альтернативное представление избыточных счетчиков. Вместо одной записи на цифру можно использовать одну запись на блок одинаковых цифр. Инкрементирование любой цифры можно выполнить за время , используя это альтернативное представление. Преимущество такого представления — возможность расширить счетчик на произвольное число одинаковых цифр за постоянное время.
Г.Бродал описывает кучевидную структуру, которая теоретически лучше, чем толстые кучи, так как их временная оценка для—в худшем случае. Структура Бродала, однако, намного сложнее толстых куч.
Толстая куча
Толстая куча — это почти кучеобразный нагруженный лес.
Представление толстой кучи. Каждый узел толстой кучи будем представлять записью следующего вида:
где — ключ элемента, приписанного узлу дерева; — указатель на родителя; — указатель на ближайшего левого брата; — указатель на ближайшего правого брата; — указатель на самого левого сына; — ранг узла. Таким образом, "братья" связаны в двусвязный список при помощи указателей
и . У самого левого (правого) "брата" в этом списке указатель () заземлен.
На рис. 9.2 представлено толстое дерево
(внутри узлов указаны их ранги).
Рис. 9.2.
Толстые деревья
Основные определения
Определяем толстое дерево ранга
следующим образом:
Толстое дерево ранга ноль состоит из единственного узла.Толстое дерево ранга , для , состоит из трех деревьев
ранга , связанных так, что корни двух из них являются самыми левыми потомками корня третьего.
Ранг узла в толстом дереве определяется как ранг толстого поддерева с корнем в узле .
На рис. 9.1 приведены примеры толстых деревьев.
Рис. 9.1.
Свойства толстых деревьев:
- В толстом дереве ранга ровно узлов.Для любого натурального числа существует лес из толстых деревьев, в котором ровно узлов. Такой лес можно построить, включив в него столько деревьев ранга , каково значение -го разряда представления числа в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.Толстый лес из узлов содержит деревьев.
Доказательства этих свойств оставим читателю в качестве упражнения. Рассмотрим лес из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества. Такой лес будем называть нагруженным. Узел в нагруженном лесе назовем неправильным, если его ключ меньше ключа его родителя. Нагруженный лес назовем почти кучеобразным, если для каждого значения в нем имеется не более двух неправильных узлов ранга .
