Пример
(рис 5.1) Первое свойство непосредственно следует из определения левостороннего дерева. Для доказательства второго свойства рассмотрим левостороннее дерево $$T$$, у которого длина правой ветви равна $$h$$. Индукцией по числу $$h$$ докажем, что число $$n$$ узлов в таком дереве удовлетворяет неравенству $$n \ge 2^h - 1$$. Действительно, при $$h= 1$$ утверждение очевидно. При $$h > 1$$ левое и правое поддеревья дерева $$T$$ будут левосторонними, а ранги их корней больше или равны $$h - 1$$. Следовательно, по предположению индукции число узлов в каждом из них больше или равно $$2^{h - 1} - 1$$, а в дереве $$T$$ — больше или равно$$\eq*{ (2^{h - 1} - 1) + (2^{h - 1} - 1) + 1 = 2^h - 1. }$$
Для реализации приоритетной очереди с помощью левосторонней кучи будем использовать узлы вида$$\eq*{ {\rm Node} = (\t element, \t key, \t rank, \t left, \t right, \t parent), }$$ содержащие следующую информацию:
Куча представляется указателем на ее корень. Если $$h$$ —
указатель на
корень кучи, то через $$h$$ будем обозначать и саму кучу. Заметим, что
указатель на родителя используется лишь в операциях
Рассмотрим процесс слияния двух левосторонних куч $$h_1$$ и $$h_2$$, изображенных на рис. 5.2.
(рис 5.2) Числа внутри кружочков являются ключами элементов, приписанных к соответствующим узлам. Правые ветви куч показаны жирными линиями. Числа рядом с узлами — их ранги.
После объединения правых путей получим дерево, изображенное
на рис. 5.3. Оно не является левосторонним.
В скобках указаны
Восстановление свойства левизны кучи начинаем с последнего узла правой ветви. Это узел с ключом $$18$$. Очевидно, он должен иметь ранг $$1$$, совпадающий с его старым значением и поэтому не требующий обновления.
(рис 5.3) Следующий по направлению к корню узел правой ветви имеет ключ $$8$$, ранг его левого сына не меньше ранга правого сына, следовательно, условие левизны выполняется и поэтому транспонирования его левого и правого поддеревьев не требуется. Однако ранг этого узла необходимо обновить, так как его старое значение $$1$$ не совпадает с увеличенным на $$1$$ минимальным из рангов его потомков, то есть с числом 2. Обновив ранг, получим кучу, изображенную на рис. 5.4.
(рис 5.4) Теперь рассмотрим узел с ключом $$7$$. Он имеет левого сына с ключом $$37$$ и рангом $$1$$ и правого сына с ключом $$8$$ и рангом $$2$$. Для восстановления свойства левизны в этом узле необходимо поменять местами его левое и правое поддеревья и обновить ранг. Его новым значением будет минимум из рангов его потомков (это ранг нового правого сына) плюс $$1$$, то есть $$2$$. В результате получаем дерево, изображенное на рис. 5.5.
(рис 5.5) Далее рассматриваем узел с ключом $$6$$. Оба его сына имеют одинаковый ранг $$2$$, следовательно, менять их местами не требуется. Вычислим лишь новое значение ранга: оно равно минимальному из рангов его детей (рангу правого сына) плюс~ $$1$$, то есть $$3$$. Получаем дерево, изображенное на рис.5.6.
(рис 5.6) Наконец, рассматриваем узел с ключом $$3$$, который является последним в правой ветви, полученной слиянием правых ветвей исходных куч. Его потомков (узлы с ключами $$10$$ и $$6$$ ) необходимо поменять местами для восстановления свойства левизны и обновить ранг, который будет теперь равен $$3$$. После выполнения этих операций получим левостороннюю кучу, изображенную на рис.5.7. На этом выполнение операции СЛИЯНИЕ заканчивается.
(рис 5.7) Очевидно, время выполнения операции СЛИЯНИЕ пропорционально сумме длин правых путей сливаемых куч. По свойству левосторонней кучи оно не превосходит величины $$\log n_1 + \log n_2 < \log n + \log n$$, где $$n_1$$, $$n_2$$ — количества узлов в исходных кучах, а $$n = n_1 + n_2$$ — количество узлов в результирующей куче. Следовательно, вычислительная сложность операции СЛИЯНИЕ равна $$O(\log n)$$.
$$\formula{ \t{ procedure ВСТАВКА}(x,\,k,\,h);\\ \t begin\\ \mbox{}\q {\rm CREATE}\ {\rm node}\ h1: [\t{element}, \t{key}, \t{rank}, \t{left}, \t{right}, \t{parent}] = [x, k, l,\\ \mbox{}\q {\rm nil}, {\rm nil}, {\rm nil}];\\ \mbox{}\q \t{СЛИЯНИЕ}(h,\,h1,\,h2);\ h := h2\\ \t end; }$$
$$\formula{ \t{procedure УДАЛЕНИЕ\_МИНИМУМА} (h, {\rm xMin});\\ \t begin\\ \mbox{}\q {\rm xMin} := h\t{\^{}}.{\rm element};\ \t{СЛИЯНИЕ}\ (h\t{\^{}}.{\rm left},\ h\t{\^{}}.{\rm right},\ h3);\ h := h3\\ \t end; }$$
$$\formula{ \t{function МИНИМУМ}\ (h);\\ \t begin\ \t{МИНИМУМ} := h\t{\^{}}.{\rm element}\\ \t end; }$$
Таким образом, время выполнения операции — $$O(\log n)$$.
Рассмотрим пример выполнения данной операции. Пусть из кучи $$h$$, изображенной на рис. 5.8, необходимо удалить элемент $$x$$ с ключом $$9$$.
(рис 5.8) Сначала отрывается подкуча $$h_2$$ с корнем $$x$$. От $$h$$ остаются куча $$h_1$$ (нелевосторонняя, так как свойству левизны не удовлетворяет узел $$p$$ ) и левосторонняя куча $$h_2$$ (рис. 5.9).
(рис 5.9) Затем удаляется узел $$x$$, а его левая и правая подкучи $$h_{2L}$$ и $$h_{2R}$$ сливаются в одну кучу $$h'_{2}$$ при помощи описанной выше операции СЛИЯНИЕ; см. рис. 5.10.
(рис 5.10) Поскольку узел $$x$$ не являлся корнем кучи $$h$$, операция еще не завершена. Куча $$h'_{2}$$ становится левым поддеревом узла $$p$$, так как узел $$x$$ был его левым сыном (рис. 5.11).
(рис 5.11) Следуем от узла $$p$$ к корню дерева, для каждого узла этого пути
восстанавливаем свойство левизны и ранг.
Сначала проверяем узел $$p$$:
его детей надо поменять местами, так как
(рис 5.12) Следующий узел на пути к корню — это родитель узла $$p$$ с ключом, равным 2. Ранги его сыновей равны, значит менять их местами не нужно. Однако его собственный ранг, возможно, требует обновления, новое значение равно рангу его правого сына плюс 1, т.е. старому: $$3$$. В результате получается дерево, изображенное на рис. 5.13.
(рис 5.13) Поскольку узел с ключом $$2$$ является корнем дерева, операция УДАЛЕНИЕ завершена.
$$\formula{ \t{procedure УДАЛЕНИЕ} (h, {\rm pos});\\ \t begin\\ \mbox{}\q \t if\ {\rm pos} = h\ \t then\ \{ \t{УДАЛЕНИЕ\_МИНИМУМА}\ (h, {\rm xMin});\ {\rm exit}\};\\ \mbox{}\q p := {\rm pos}\t{\^{}}.{\rm parent};\ h2 := {\rm pos};\ \t{УДАЛЕНИЕ\_МИНИМУМА}\ (h2, {\rm xMin});\\ \mbox{}\q \t if\ p\t{\^{}}.{\rm left} = {\rm pos}\ \t then\ p\t{\^{}}.{\rm left} := h2\ \t else\ p\t{\^{}}. {\rm right} := h2;\\ \mbox{}\q \t while\ p \ne {\rm nil}\ \t do\\ \mbox{}\q \t begin\\ \mbox{}\q \t if\ p\t{\^{}}.{\rm left} \ne {\rm nil}\ \t then\ r1:= p\t{\^{}}.{\rm left}\t{\^{}}.{\rm rank}\ \t else\ r1:= 0;\\ \mbox{}\q \t if\ p \t{\^{}}.{\rm right} \ne {\rm nil}\ \t then\ r2:= p\t{\^{}}.{\rm right}\t{\^{}}.{\rm rank}\ \t else\ r2:= 0;\\ \mbox{}\qq {\rm newrank} := {\rm min} (r1, r2) + 1;\\ \mbox{}\q \t if\ r1 < r2\ \t then\ {\rm tr}\ (p\t{\^{}}. {\rm left},\ p\t{\^{}}.{\rm right});\\ \mbox{}\q \t if\ {\rm newrank} \ne p\t{\^{}}.{\rm parent}\t{\^{}}.{\rm rank}\ \t then\ p\t{\^{}}.{\rm parent}\t{\^{}}.{\rm rank} := {\rm newrank}\\ \mbox{}\q \t else\ \t{exit};\\ \mbox{}\q p:= p\t{\^{}}.{\rm parent};\\ \mbox{}\q \t end\\ \t end }$$
От исходной кучи $$h$$ отрывается подкуча $$h_2$$ с корнем в узле $$x$$. Оставшаяся куча $$h$$ не обязательно будет левосторонней. Затем ключ узла $$x$$ уменьшается на заданное число $$\Dl$$. Куча $$h_2$$ при этом все еще остается левосторонней.
В куче $$h$$ восстанавливается свойство левизны, как — показано далее. Фактически свойству левизны могут не удовлетворять только узлы, находящиеся на пути от $$p$$ ( $$p$$ — родитель узла $$x$$ ) до корня $$h$$. Длина этого пути в худшем случае линейно зависит от $$n$$. Но на самом деле нам нужно проверить только первые не более чем $$\lfloor \log (n + 1)\rfloor$$ узлов на этом пути. Наконец, куча $$h$$ сливается с $$h_2$$ за время $$O(\log n)$$. Таким образом, время выполнения данной операции — $$O(\log n)$$.
Рассмотрим пример. Пусть в куче, изображенной на рис. 5.14, необходимо уменьшить ключ узла $$x$$ от $$9$$ до $$0$$.
(рис 5.14) Делается это следующим образом. От исходной кучи $$h$$ отрывается подкуча $$h_2$$ с корнем в удаляемом узле $$x$$. Теперь куча $$h$$ не является левосторонней, так как в узле $$p$$ нарушено свойство левизны (рис. 5.15).
(рис 5.15) Ключ узла $$x$$ уменьшается до 0, куча $$h_2$$ при этом все еще остается левосторонней (рис. 5.16).
(рис 5.16) Следуем от узла $$p$$ до корня дерева $$h$$, для каждого
узла этого пути восстанавливаем свойство левизны и ранг.
Сначала проверяем узел $$p$$: его детей надо поменять местами
(а фактически — только
одного-единственного правого сына сделать левым). После этого вычисляется
новый
(рис 5.17) Следующий узел — это родитель узла $$p$$
с ключом $$2$$. Его потомков тоже
необходимо поменять местами (так как ранг левого сына меньше ранга
правого). После этого
(рис 5.18) Наконец, сливаем кучи $$h$$ и $$h_2$$, получая в результате левостороннюю кучу (рис. 5.19).
(рис 5.19) $$\formula{ \t{procedure УМЕНЬШИТЬ\_КЛЮЧ} (h, {\rm pos}, {\rm delta});\\ \t begin\\ \mbox{}\q {\rm pos}\t{\^{}}.{\rm key} := {\rm pos}\t{\^{}}.{\rm key} - {\rm delta};\ \t if\ {\rm pos} = h\ \t then\ {\rm exit};\\ \mbox{}\q p := {\rm pos}\t{\^{}}.{\rm parent};\ h2 := {\rm pos};\\ \mbox{}\q \t if\ p\t{\^{}}.{\rm left} = {\rm pos}\ \t then\ p\t{\^{}}.{\rm left} := {\rm nil}\ \t else\ \t if\ p\t{\^{}}.{\rm right} = {\rm pos}\ \t then\\ \mbox{}\q\qq p\t{\^{}}.{\rm right} := {\rm nil};\\ \mbox{}\q \t while\ p \ne {\rm nil}\ \t do\\ \mbox{}\q \t begin\\ \mbox{}\q\qq \t if\ p\t{\^{}}.{\rm left} \ne {\rm nil}\ \t then\ r1 := p\t{\^{}}.{\rm left}\t{\^{}}.{\rm rank}\ \t else\ r1 := 0;\\ \mbox{}\q\qq \t if\ p\t{\^{}}.{\rm right} \ne {\rm nil}\ \t then\ r2 := p\t{\^{}}.{\rm right}\t{\^{}}.{\rm rank}\ \t else\ r2 := 0;\\ \mbox{}\q\qq {\rm newrank} := {\rm min} (r1, r2 ) + 1;\\ \mbox{}\q\qq \t if\ r1 < r2\ \t then\ {\rm tr} (p\t{\^{}}.{\rm left},\ p\t{\^{}}.{\rm right});\\ \mbox{}\q\qq \t if\ {\rm newrank} \ne p\t{\^{}}.{\rm parent}\t{\^{}}. {\rm rank}\ \t then\\ \mbox{}\q\qq\qq p\t{\^{}}.{\rm parent}\t{\^{}}.{\rm rank} := {\rm newrank}\ \t else\ {\rm exit};\\ \mbox{}\q\qq p := p\t{\^{}}.{\rm parent}\\ \mbox{}\q \t end;\\ \mbox{}\q \t{СЛИЯНИЕ}\ (h,\,h2,\,h);\\ \t end; }$$
Более эффективным является следующий способ образования $$n$$ -элементной левосторонней кучи. Заводится список $$Q$$, в который помещаются $$n$$ одноэлементных куч. Пока длина списка $$Q$$ больше 1, из его начала извлекаются две кучи, производится их слияние, а полученная куча вставляется в конец списка $$Q$$.
Читателю предоставляется возможность доказать, что время выполнения операции ОБРАЗОВАТЬ_ОЧЕРЕДЬ таким способом — $$O(n)$$.
$$\formula{ \t{procedure ОБРАЗОВАТЬ\_ОЧЕРЕДЬ}\ (S, h);\\ \t begin\\ \mbox{}\q \t{Создать список Q из одноэлементных куч, содержащих элементы}\\ \mbox{}\q \t{списка}\ S;\\ \mbox{}\q \t while\ |Q| > 1\ \t do\\ \mbox{}\q \t begin\\ \mbox{}\q\qq \t{Из начала списка}\ Q\ \t{изъять две кучи}\ h1, h2;\\ \mbox{}\q\qq \t{Создать кучу}\ h,\ \t{объединяя кучи}\ h1, h2;\\ \mbox{}\q\qq \t{Поместить кучу}\ h\ \t{в конец списка}\ Q\\ \mbox{}\q \t end\\ \t end; }$$
| СЛИТЬ $$(h1, h2, h)$$ | $$O(\log n)$$ |
| ВСТАВИТЬ $$(x, h)$$ | $$O(\log n)$$ |
| УДАЛИТЬ_МИН $$(h, x)$$ | $$O(\log n)$$ |
| МИН $$(x, h)$$ | $$O(1)$$ |
| УДАЛИТЬ $$(x, h)$$ | $$O(\log n)$$ |
| УМЕНЬШИТЬ_КЛЮЧ $$(x, D, h)$$ | $$O(\log n)$$ |
| ОБРАЗОВАТЬ_ОЧЕРЕДЬ $$(q, h)$$ | $$O(n)$$ |
Пример
(рис 5.1) Первое свойство непосредственно следует из определения левостороннего дерева. Для доказательства второго свойства рассмотрим левостороннее дерево $$T$$, у которого длина правой ветви равна $$h$$. Индукцией по числу $$h$$ докажем, что число $$n$$ узлов в таком дереве удовлетворяет неравенству $$n \ge 2^h - 1$$. Действительно, при $$h= 1$$ утверждение очевидно. При $$h > 1$$ левое и правое поддеревья дерева $$T$$ будут левосторонними, а ранги их корней больше или равны $$h - 1$$. Следовательно, по предположению индукции число узлов в каждом из них больше или равно $$2^{h - 1} - 1$$, а в дереве $$T$$ — больше или равно$$\eq*{ (2^{h - 1} - 1) + (2^{h - 1} - 1) + 1 = 2^h - 1. }$$
Для реализации приоритетной очереди с помощью левосторонней кучи будем использовать узлы вида$$\eq*{ {\rm Node} = (\t element, \t key, \t rank, \t left, \t right, \t parent), }$$ содержащие следующую информацию:
Куча представляется указателем на ее корень. Если $$h$$ —
указатель на
корень кучи, то через $$h$$ будем обозначать и саму кучу. Заметим, что
указатель на родителя используется лишь в операциях
Рассмотрим процесс слияния двух левосторонних куч $$h_1$$ и $$h_2$$, изображенных на рис. 5.2.
(рис 5.2) Числа внутри кружочков являются ключами элементов, приписанных к соответствующим узлам. Правые ветви куч показаны жирными линиями. Числа рядом с узлами — их ранги.
После объединения правых путей получим дерево, изображенное
на рис. 5.3. Оно не является левосторонним.
В скобках указаны
Восстановление свойства левизны кучи начинаем с последнего узла правой ветви. Это узел с ключом $$18$$. Очевидно, он должен иметь ранг $$1$$, совпадающий с его старым значением и поэтому не требующий обновления.
(рис 5.3) Следующий по направлению к корню узел правой ветви имеет ключ $$8$$, ранг его левого сына не меньше ранга правого сына, следовательно, условие левизны выполняется и поэтому транспонирования его левого и правого поддеревьев не требуется. Однако ранг этого узла необходимо обновить, так как его старое значение $$1$$ не совпадает с увеличенным на $$1$$ минимальным из рангов его потомков, то есть с числом 2. Обновив ранг, получим кучу, изображенную на рис. 5.4.
(рис 5.4) Теперь рассмотрим узел с ключом $$7$$. Он имеет левого сына с ключом $$37$$ и рангом $$1$$ и правого сына с ключом $$8$$ и рангом $$2$$. Для восстановления свойства левизны в этом узле необходимо поменять местами его левое и правое поддеревья и обновить ранг. Его новым значением будет минимум из рангов его потомков (это ранг нового правого сына) плюс $$1$$, то есть $$2$$. В результате получаем дерево, изображенное на рис. 5.5.
(рис 5.5) Далее рассматриваем узел с ключом $$6$$. Оба его сына имеют одинаковый ранг $$2$$, следовательно, менять их местами не требуется. Вычислим лишь новое значение ранга: оно равно минимальному из рангов его детей (рангу правого сына) плюс~ $$1$$, то есть $$3$$. Получаем дерево, изображенное на рис.5.6.
(рис 5.6) Наконец, рассматриваем узел с ключом $$3$$, который является последним в правой ветви, полученной слиянием правых ветвей исходных куч. Его потомков (узлы с ключами $$10$$ и $$6$$ ) необходимо поменять местами для восстановления свойства левизны и обновить ранг, который будет теперь равен $$3$$. После выполнения этих операций получим левостороннюю кучу, изображенную на рис.5.7. На этом выполнение операции СЛИЯНИЕ заканчивается.
(рис 5.7) Очевидно, время выполнения операции СЛИЯНИЕ пропорционально сумме длин правых путей сливаемых куч. По свойству левосторонней кучи оно не превосходит величины $$\log n_1 + \log n_2 < \log n + \log n$$, где $$n_1$$, $$n_2$$ — количества узлов в исходных кучах, а $$n = n_1 + n_2$$ — количество узлов в результирующей куче. Следовательно, вычислительная сложность операции СЛИЯНИЕ равна $$O(\log n)$$.
$$\formula{ \t{ procedure ВСТАВКА}(x,\,k,\,h);\\ \t begin\\ \mbox{}\q {\rm CREATE}\ {\rm node}\ h1: [\t{element}, \t{key}, \t{rank}, \t{left}, \t{right}, \t{parent}] = [x, k, l,\\ \mbox{}\q {\rm nil}, {\rm nil}, {\rm nil}];\\ \mbox{}\q \t{СЛИЯНИЕ}(h,\,h1,\,h2);\ h := h2\\ \t end; }$$
$$\formula{ \t{procedure УДАЛЕНИЕ\_МИНИМУМА} (h, {\rm xMin});\\ \t begin\\ \mbox{}\q {\rm xMin} := h\t{\^{}}.{\rm element};\ \t{СЛИЯНИЕ}\ (h\t{\^{}}.{\rm left},\ h\t{\^{}}.{\rm right},\ h3);\ h := h3\\ \t end; }$$
$$\formula{ \t{function МИНИМУМ}\ (h);\\ \t begin\ \t{МИНИМУМ} := h\t{\^{}}.{\rm element}\\ \t end; }$$
Таким образом, время выполнения операции — $$O(\log n)$$.
Рассмотрим пример выполнения данной операции. Пусть из кучи $$h$$, изображенной на рис. 5.8, необходимо удалить элемент $$x$$ с ключом $$9$$.
(рис 5.8) Сначала отрывается подкуча $$h_2$$ с корнем $$x$$. От $$h$$ остаются куча $$h_1$$ (нелевосторонняя, так как свойству левизны не удовлетворяет узел $$p$$ ) и левосторонняя куча $$h_2$$ (рис. 5.9).
(рис 5.9) Затем удаляется узел $$x$$, а его левая и правая подкучи $$h_{2L}$$ и $$h_{2R}$$ сливаются в одну кучу $$h'_{2}$$ при помощи описанной выше операции СЛИЯНИЕ; см. рис. 5.10.
(рис 5.10) Поскольку узел $$x$$ не являлся корнем кучи $$h$$, операция еще не завершена. Куча $$h'_{2}$$ становится левым поддеревом узла $$p$$, так как узел $$x$$ был его левым сыном (рис. 5.11).
(рис 5.11) Следуем от узла $$p$$ к корню дерева, для каждого узла этого пути
восстанавливаем свойство левизны и ранг.
Сначала проверяем узел $$p$$:
его детей надо поменять местами, так как
(рис 5.12) Следующий узел на пути к корню — это родитель узла $$p$$ с ключом, равным 2. Ранги его сыновей равны, значит менять их местами не нужно. Однако его собственный ранг, возможно, требует обновления, новое значение равно рангу его правого сына плюс 1, т.е. старому: $$3$$. В результате получается дерево, изображенное на рис. 5.13.
(рис 5.13) Поскольку узел с ключом $$2$$ является корнем дерева, операция УДАЛЕНИЕ завершена.
$$\formula{ \t{procedure УДАЛЕНИЕ} (h, {\rm pos});\\ \t begin\\ \mbox{}\q \t if\ {\rm pos} = h\ \t then\ \{ \t{УДАЛЕНИЕ\_МИНИМУМА}\ (h, {\rm xMin});\ {\rm exit}\};\\ \mbox{}\q p := {\rm pos}\t{\^{}}.{\rm parent};\ h2 := {\rm pos};\ \t{УДАЛЕНИЕ\_МИНИМУМА}\ (h2, {\rm xMin});\\ \mbox{}\q \t if\ p\t{\^{}}.{\rm left} = {\rm pos}\ \t then\ p\t{\^{}}.{\rm left} := h2\ \t else\ p\t{\^{}}. {\rm right} := h2;\\ \mbox{}\q \t while\ p \ne {\rm nil}\ \t do\\ \mbox{}\q \t begin\\ \mbox{}\q \t if\ p\t{\^{}}.{\rm left} \ne {\rm nil}\ \t then\ r1:= p\t{\^{}}.{\rm left}\t{\^{}}.{\rm rank}\ \t else\ r1:= 0;\\ \mbox{}\q \t if\ p \t{\^{}}.{\rm right} \ne {\rm nil}\ \t then\ r2:= p\t{\^{}}.{\rm right}\t{\^{}}.{\rm rank}\ \t else\ r2:= 0;\\ \mbox{}\qq {\rm newrank} := {\rm min} (r1, r2) + 1;\\ \mbox{}\q \t if\ r1 < r2\ \t then\ {\rm tr}\ (p\t{\^{}}. {\rm left},\ p\t{\^{}}.{\rm right});\\ \mbox{}\q \t if\ {\rm newrank} \ne p\t{\^{}}.{\rm parent}\t{\^{}}.{\rm rank}\ \t then\ p\t{\^{}}.{\rm parent}\t{\^{}}.{\rm rank} := {\rm newrank}\\ \mbox{}\q \t else\ \t{exit};\\ \mbox{}\q p:= p\t{\^{}}.{\rm parent};\\ \mbox{}\q \t end\\ \t end }$$
От исходной кучи $$h$$ отрывается подкуча $$h_2$$ с корнем в узле $$x$$. Оставшаяся куча $$h$$ не обязательно будет левосторонней. Затем ключ узла $$x$$ уменьшается на заданное число $$\Dl$$. Куча $$h_2$$ при этом все еще остается левосторонней.
В куче $$h$$ восстанавливается свойство левизны, как — показано далее. Фактически свойству левизны могут не удовлетворять только узлы, находящиеся на пути от $$p$$ ( $$p$$ — родитель узла $$x$$ ) до корня $$h$$. Длина этого пути в худшем случае линейно зависит от $$n$$. Но на самом деле нам нужно проверить только первые не более чем $$\lfloor \log (n + 1)\rfloor$$ узлов на этом пути. Наконец, куча $$h$$ сливается с $$h_2$$ за время $$O(\log n)$$. Таким образом, время выполнения данной операции — $$O(\log n)$$.
Рассмотрим пример. Пусть в куче, изображенной на рис. 5.14, необходимо уменьшить ключ узла $$x$$ от $$9$$ до $$0$$.
(рис 5.14) Делается это следующим образом. От исходной кучи $$h$$ отрывается подкуча $$h_2$$ с корнем в удаляемом узле $$x$$. Теперь куча $$h$$ не является левосторонней, так как в узле $$p$$ нарушено свойство левизны (рис. 5.15).
(рис 5.15) Ключ узла $$x$$ уменьшается до 0, куча $$h_2$$ при этом все еще остается левосторонней (рис. 5.16).
(рис 5.16) Следуем от узла $$p$$ до корня дерева $$h$$, для каждого
узла этого пути восстанавливаем свойство левизны и ранг.
Сначала проверяем узел $$p$$: его детей надо поменять местами
(а фактически — только
одного-единственного правого сына сделать левым). После этого вычисляется
новый
(рис 5.17) Следующий узел — это родитель узла $$p$$
с ключом $$2$$. Его потомков тоже
необходимо поменять местами (так как ранг левого сына меньше ранга
правого). После этого
(рис 5.18) Наконец, сливаем кучи $$h$$ и $$h_2$$, получая в результате левостороннюю кучу (рис. 5.19).
(рис 5.19) $$\formula{ \t{procedure УМЕНЬШИТЬ\_КЛЮЧ} (h, {\rm pos}, {\rm delta});\\ \t begin\\ \mbox{}\q {\rm pos}\t{\^{}}.{\rm key} := {\rm pos}\t{\^{}}.{\rm key} - {\rm delta};\ \t if\ {\rm pos} = h\ \t then\ {\rm exit};\\ \mbox{}\q p := {\rm pos}\t{\^{}}.{\rm parent};\ h2 := {\rm pos};\\ \mbox{}\q \t if\ p\t{\^{}}.{\rm left} = {\rm pos}\ \t then\ p\t{\^{}}.{\rm left} := {\rm nil}\ \t else\ \t if\ p\t{\^{}}.{\rm right} = {\rm pos}\ \t then\\ \mbox{}\q\qq p\t{\^{}}.{\rm right} := {\rm nil};\\ \mbox{}\q \t while\ p \ne {\rm nil}\ \t do\\ \mbox{}\q \t begin\\ \mbox{}\q\qq \t if\ p\t{\^{}}.{\rm left} \ne {\rm nil}\ \t then\ r1 := p\t{\^{}}.{\rm left}\t{\^{}}.{\rm rank}\ \t else\ r1 := 0;\\ \mbox{}\q\qq \t if\ p\t{\^{}}.{\rm right} \ne {\rm nil}\ \t then\ r2 := p\t{\^{}}.{\rm right}\t{\^{}}.{\rm rank}\ \t else\ r2 := 0;\\ \mbox{}\q\qq {\rm newrank} := {\rm min} (r1, r2 ) + 1;\\ \mbox{}\q\qq \t if\ r1 < r2\ \t then\ {\rm tr} (p\t{\^{}}.{\rm left},\ p\t{\^{}}.{\rm right});\\ \mbox{}\q\qq \t if\ {\rm newrank} \ne p\t{\^{}}.{\rm parent}\t{\^{}}. {\rm rank}\ \t then\\ \mbox{}\q\qq\qq p\t{\^{}}.{\rm parent}\t{\^{}}.{\rm rank} := {\rm newrank}\ \t else\ {\rm exit};\\ \mbox{}\q\qq p := p\t{\^{}}.{\rm parent}\\ \mbox{}\q \t end;\\ \mbox{}\q \t{СЛИЯНИЕ}\ (h,\,h2,\,h);\\ \t end; }$$
Более эффективным является следующий способ образования $$n$$ -элементной левосторонней кучи. Заводится список $$Q$$, в который помещаются $$n$$ одноэлементных куч. Пока длина списка $$Q$$ больше 1, из его начала извлекаются две кучи, производится их слияние, а полученная куча вставляется в конец списка $$Q$$.
Читателю предоставляется возможность доказать, что время выполнения операции ОБРАЗОВАТЬ_ОЧЕРЕДЬ таким способом — $$O(n)$$.
$$\formula{ \t{procedure ОБРАЗОВАТЬ\_ОЧЕРЕДЬ}\ (S, h);\\ \t begin\\ \mbox{}\q \t{Создать список Q из одноэлементных куч, содержащих элементы}\\ \mbox{}\q \t{списка}\ S;\\ \mbox{}\q \t while\ |Q| > 1\ \t do\\ \mbox{}\q \t begin\\ \mbox{}\q\qq \t{Из начала списка}\ Q\ \t{изъять две кучи}\ h1, h2;\\ \mbox{}\q\qq \t{Создать кучу}\ h,\ \t{объединяя кучи}\ h1, h2;\\ \mbox{}\q\qq \t{Поместить кучу}\ h\ \t{в конец списка}\ Q\\ \mbox{}\q \t end\\ \t end; }$$
| СЛИТЬ $$(h1, h2, h)$$ | $$O(\log n)$$ |
| ВСТАВИТЬ $$(x, h)$$ | $$O(\log n)$$ |
| УДАЛИТЬ_МИН $$(h, x)$$ | $$O(\log n)$$ |
| МИН $$(x, h)$$ | $$O(1)$$ |
| УДАЛИТЬ $$(x, h)$$ | $$O(\log n)$$ |
| УМЕНЬШИТЬ_КЛЮЧ $$(x, D, h)$$ | $$O(\log n)$$ |
| ОБРАЗОВАТЬ_ОЧЕРЕДЬ $$(q, h)$$ | $$O(n)$$ |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.