Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
НР Оптимизация алгоритмов на графах с помощью 2-3 куч.docx
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
969 Кб
Скачать
☆

3.2 Извлечение приоритетного элемента из кучи. Поиск. Слияние

Три алгоритма были объединены под одним заголовком, так как они являются тривиальными, в отличие от вставки.

Далее на очереди алгоритм извлечения приоритетного.

Алгоритм извлечения определим, как обратный алгоритму вставки. Если алгоритм вставки выполняется по формулам:

nf + nf = nt

nf + nt = (n+1)f

то извлечение будет разбивать деревья по правилам:

nf = (n-1)t + p + x

nt = (n-1)t + nf + p + x

где p – приоритетный элемент, который мы извлекаем.

X – сосед вершины (n-1) t, которого также необходимо заново вставить.

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

В случае с насыщенным деревом отсоединяем корневую вершину от соседа и сына, затем вставляем сына в кучу заново (степень соседа не изменилась, поэтому ему менять позицию не надо).

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

Рисунок 3.10: Пример разбиения 2t = 1t + 2f + x

Алгоритм поиска ищет приоритетный элемент за (Если хранить указатель на приоритетный , то за ). Последующие операции выполняют вставку за . Таких вставок штук. Итого извлечение приоритетного элемента выполняется за ).

Алгоритм слияния выглядит достаточно очевидно: вырезаем дерево из кучи b, и вставляем ее в кучу a.Вставка производиться за . Значит и сложность операции .

3.3 Изменение ключа произвольного элемента кучи

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

  1. Родитель более приоритетнее, либо NULL

  2. Сын менее приоритетнее, либо NULL

  3. Если сосед присутствует, и он более приоритетный, то он помечен, иначе помечена сама вершина.

  4. Левый сосед менее приоритетный, правый более приоритетный если степень левого соседа больше степени правого соседа (ограничение в силу цикличности).

Тогда алгоритм изменения ключа определим, как установку ключа в необходимое значение, а затем восстановление свойств кучи. Алгоритм можно назвать алгоритмов приоритетного просеивания. Если мы сделали элемент более приоритетным, он будет стремиться к корневой вершине, для этого мы будем в первую очередь меняться местами с соседом справа при условии, что его степень больше чем степень текущей вершины. Проверка и обработка левого соседа в дополнении с правым на практике прироста к скорости не дало. Поэтому ее мы проводить не будем. Далее проверяем партнера. Больший по приоритету всегда помеченный партнер, поэтому если приоритет нашего элемента больше, и он не помеченный, то меняем его местами с партнером. Если приоритет меньше, то делаем наоборот. Далее проверяем родителя. С родителем меняемся только в том случае, если наша вершина приоритетнее. И наконец проверяем сына, если сын приоритетнее вершины, меняемся с ним. Алгоритм повторяется до тех пор, пока не будет произведено холостого прохода, то есть пока свойства кучи не восстановятся.

На рисунке 3.11 изображен пример работы алгоритма

Рисунок 3.11: Изменение ключа 9 на 2, а затем 1 на 99

Путь к самой отдаленной от корня вершине равен степени дерева, следовательно, сложность алгоритма равна