Задачи к главе 20

417

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

20.2-10 Покажите, что время работы процедур Binomial-Heap-Extract-Min, Binomial-Heap-Decrease-Key и Binomial-Heap-Delete в худшем случае на входах размера га есть fi(lgn).

Объясните, почему время выполнения процедур Binomial-Heap-Insert и Binomial-Heap-Minimum в худшем случае соста-

оо

вляет fi(lgn) (см. зад. 2-5), а не Q(lgn).

Задачи

20-1 2-3-4-кучи

В главе 19 рассматривались 2-3-4-деревья, в которых каждая вершина, не являющаяся корнем или листом, имеет двух, трех или четырёх детей, и все листья располагаются на одинаковой глубине. Определим 2-3-4-кучи (2-3-4 heaps), над которыми можно производить операции, предусмотренные для сливаемых куч.

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

Придумайте способ реализации перечисленных ниже операций над 2-3-4-кучами за время О (lgra), где га - число элементов 2-3-4-кучи. Операция Union в пункте е должна выполняться за время О (lgra), где га - суммарное число элементов в двух объединяемых кучах.

а.Minimum возвращает указатель на лист с наименьшим ключом.

б.Decrease-Key уменьшает ключ заданного листа ж, присваивая ключу заданное значение k кеу[х].

в.Insert добавляет лист ж с ключом к.

г.Delete удаляет заданный лист ж.

д.Extract-Min изымает лист с наименьшим ключом.

е.Union объединяет две 2-3-4-кучи в одну (исходные кучи пропадают).

20-2 Поиск минимального покрывающего дерева с использованием сливаемых куч

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

Пусть G = (V, Е) - связный неориентированный граф, аю: R - весовая функция, ставящая в соответствие каждому ребру (и, v) его вес w(u,v). Мы хотим найти минимальное покрывающее дерево графа G, т.е. ациклическое множество Т С Е, которое соединяет все вершины графа, для которого суммарный вес w(T) =w(u, v) минимален.

Следующая программа (её корректность доказывается с использованием методов раздела 24.1) строит минимальное покрывающее дерево Т. Программа хранит разбиение {Vi} множества вершин V, и для каждого из множеств Vi хранит некоторое множество

Опишите, как реализовать этот алгоритм с помощью операций со сливаемыми кучами, перечисленных в таблице 20.1. Оцените время работы алгоритма, если в качестве сливаемых куч используются биномиальные кучи.

(u,v)eT

Ei С {(и, v) : и G Vi или v £ Vi}

рёбер, инцидентных вершинам из Vi.

Замечания

Биномиальные кучи были введены в 1978 году Виллемином [196]. Подробно их свойства изучал Браун [36,37].

Фибоначчиевы кучи

В главе 20 мы изучали биномиальные кучи, с помощью которых можно реализовать за время О (lgra) (в худшем случае) операции Insert, Minimum, Extract-Min, Union, а также Decrease-Key и Delete. (Структуры данных, поддерживающие первые четыре из перечисленных операций, называются «сливаемыми кучами».) В этой главе мы рассматриваем фибоначчиевы кучи, которые поддерживают те же шесть операций, но более эффективно: операции, не требующие удаления элементов, имеют учётную стоимость 0(1).

Теоретически фибоначчиевы кучи особенно полезны, если число операций Extract-Min и Delete мало по сравнению с остальными операциями. Такая ситуация возникает во многих приложениях. Например, алгоритм, обрабатывающий граф, может вызывать процедуру Decrease-Key для каждого ребра графа. Для плотных графов, имеющих много рёбер, переход от O(lgra) к 0(1) в оценке времени работы для операции Decrease-Key может привести к заметному уменьшению общего времени работы. Наиболее быстрые известные алгоритмы для задач построения минимального покрывающего дерева (глава 24) или поиска кратчайших путей из одной вершины (глава 25) существенно используют фибоначчиевы кучи.

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

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

Если мы никогда не выполняем операции Decrease-Key и Delete, то возникающие фибоначчиевы деревья будут иметь ту же структуру, что и биномиальные деревья. Но в общем случае