354 Глава 8. Кучи и приоритетные очереди

(a) (b)

(c) (d)

(e) (f)

(g) Рисунок 8.10: Наращивание кучи с 15 записями: (a) мы начинаем, строя один вход, сваливает нижний уровень в кучу; (b) и (c) мы объединяем эти кучи в кучи с тремя входами; (d) и (e) кучи с семью входами; (f) и (g) мы создаем заключительную кучу. Пути вниз-кучи bubblings подсвечены синим. Для простоты мы только показываем ключ в пределах каждого узла вместо всего входа.

8.3. Кучи 355

Рекурсивное восходящее строительство кучи

Мы можем также описать восходящее строительство кучи как рекурсивный алгоритм, как

показанный в Кодовом Фрагменте 8.18, который мы называем, передавая список, хранящий ключи, для которых мы хотим построить кучу.

Алгоритм BottomUpHeap (L):

Вход: список L STL, хранящий n = ^2h+1 - 1 записи

Продукция: куча T хранение записей L.

если L.empty () тогда

возвратите пустую кучу e¬ L.front ()

Фронт L.pop ()

Разделение L в два списка, L1 и L2, каждый размер (n- 1)/2

T1 ¬ BottomUpHeap (L1) T2 ¬ BottomUpHeap (L2)

Создайте двоичное дерево T с корнем r хранящий e, оставленный поддерево T1 и правильное поддерево T2

Выполните вниз-кучу, пузырящуюся от корня r T, если необходимое возвращение T

Кодовый Фрагмент 8.18: Рекурсивное восходящее строительство кучи.

Хотя алгоритм был выражен с точки зрения списка STL, довод «против» - struction, возможно, был выполнен одинаково хорошо с вектором. В таком случае разделение вектора выполнено концептуально, определив два ряда индексов, одно представление передней половины L1 и другого представления спины половина L2.

На первый взгляд может казаться, что нет никаких существенных различий между этим алгоритмом и возрастающим строительством кучи, используемым в алгоритме вида кучи Раздела 8.3.5. Каждый работает пузырением вниз-кучи и другим пузырением-кучи использования. Несколько удивительно, поэтому, что восходящее строительство кучи фактически асимптотически быстрее, чем возрастающая вставка n ключи в первоначально пустую кучу. Следующее суждение показывает это.

Суждение 8.7: Наращивание кучи с n записями берет O (n)

время, принимая два ключа может быть сравнено в O (1) время.

Оправдание: Мы анализируем восходящее строительство кучи, используя «визуальное» AP - proach, который иллюстрирован в рисунке 8.11.

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

356

Глава 8. Кучи и приоритетные очереди

Теперь рассмотрите путь p (v) из T от узла v его inorder преемнику внешний узел, то есть, путь, который начинается в v, идет к правильному ребенку v, и затем понижается влево, пока это не достигает внешнего узла. Мы говорим, что путь p (v) связан с узлом v. Обратите внимание на то, что p (v) является не обязательно путем, сопровождаемым пузырением вниз-кучи, формируясь T (v). Ясно, размер (число узлов) p (v) равен высоте T (v) плюс один. Следовательно, формирование T (v) занимает время пропорциональное размеру p (v) в худшем случае. Таким образом полная продолжительность восходящего строительства кучи пропорциональна сумме размеров путей, связанных с узлами T.

Заметьте, что каждый узел v T принадлежит самое большее двум таким путям: путь p (v) связался с самим v и возможно также путем p (u) связанный с самым близким предком u v, предшествующего v в inorder пересечении. (См. рисунок 8.11.) В частности корень r T и узлов на крайнем левом пути корня к листу каждый принадлежит только одному пути, тот, связанный с самим узлом. Поэтому, сумма размеров

из путей, связанных с внутренними узлами T, самое большее 2n- 1. Мы завершаем

то, что наращивание кучи T берет O (n) время.

Рисунок 8.11: Визуальное оправдание линейной продолжительности восходящего довода «против» кучи - struction, где пути, связанные с внутренними узлами, были выдвинуты на первый план с чередованием цветов. Например, путь, связанный с корнем, состоит из узлов, хранящих ключи 4, 6, 7, и 11. Кроме того, путь, связанный с правильным ребенком корня, состоит из внутренних узлов, хранящих ключи 6, 20, и 23.

Чтобы подвести итог, Предложите 8,7 государств, что продолжительность для первой фазы вида кучи может быть уменьшена, чтобы быть O (n). К сожалению, продолжительность второй фазы вида кучи не может быть сделана асимптотически лучше, чем O (n, регистрируют n) (то есть, это всегда будетW (n, регистрируют n) в худшем случае). Мы не оправдываем, это ниже связало до Главы 11, как бы то ни было. Вместо этого мы завершаем эту главу, обсуждая шаблон, который позволяет нам расширять приоритетную очередь ADT, чтобы иметь дополнительную функциональность.