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

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

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

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

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

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

 

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

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

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

 

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

Обход по куче

Мы разобрали основные алгоритмы, однако я приведу ещё один алгоритм: обход по куче. Этот алгоритм необходим для утилизации кучи и для выполнения некоторых функций, например, получение указателей на все вершины.

Обход по куче будем выполнять по аналогии с обходом деревьев рекурсивной процедурой:

Обойти сына

Обойти партнера

Обойти соседа

Выполнить функцию

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

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

Рисунок 3.12: Пример обхода дерева кучи (вершины помечены в порядке обхода)