Структуры данных и модели вычислений
Реализация основных операций и оценки трудоемкости
Сосредоточим внимание на амортизационных оценках трудоемкости. Будем получать их методом потенциалов. Потенциалом тонкой кучи будем считать величину , где — количество деревьев в куче, а — число помеченных вершин. Заметим, что потенциал кучи неотрицателен и в начальный момент равен .
Операция MakeHeap. Эта операция создает указатель на новую пустую кучу. Очевидно, фактическая стоимость операции есть , а потенциал созданной кучи равен .
Операция FindMin (H). Указатель на узел с минимальным ключом в куче определяется с помощью указателя . Если куча пуста, то результирующий указатель нулевой. Амортизационная оценка совпадает с фактической и равна , потенциал не изменяется.
Операция Insert(i,H). С помощью этой операции осуществляется вставка в кучу нового элемента с ключом . При ее реализации создается новое тонкое дерево ранга , которое вставляется в корневой список кучи , разрывая его в произвольном месте. При необходимости перевычисляется ссылка на минимальный элемент.
Операция увеличивает потенциал на , так как добавляется одно дерево в корневой список кучи, но это не влияет на амортизационную оценку, которая равна фактической .
Операция Meld(H1, H2). Результатом этой операции является указатель на кучу, полученную слиянием двух куч
и . Она осуществляется соединением корневых списков сливаемых куч. При таком способе выполнения операции, как и при реализации вставки элемента в кучу, можем получить в корневом списке результирующей кучи несколько деревьев одинакового ранга. При удобном случае, а именно при удалении минимального элемента, мы освободим корневой список от этой неоднозначности. Оценка совпадает с оценками для всех предыдущих операций. Суммарный потенциал не изменяется.
Операция DeleteMin(H). Эта операция предназначена для удаления узла с минимальным ключом из непустой кучи . Для ее реализации удаляем минимальный узел из корневого списка кучи , добавляем список детей удаленного узла в корневой список и повторяем следующий "связывающий шаг".
Находим любые два дерева, корни которых имеют одинаковые ранги, и связываем их, делая корень с большим ключом новым левым потомком корня с меньшим ключом, увеличивая ранг нового полученного тонкого дерева на единицу. При этом следует удалить из корневого списка кучи
корень с большим ключом. Как только не останется деревьев с корнями одинакового ранга, в полученном корневом списке необходимо найти элемент с минимальным ключом.
Рассмотрим теперь, с помощью каких средств реализуется связывающий шаг. Для хранения ссылок на корни деревьев используем временный массив , размера . Величина будет указателем на тонкое дерево ранга . Если найдется еще одно дерево ранга , то свяжем два дерева ранга в одно дерево ранга , в -й ячейке массива установим нулевой указатель и продолжим связывающую процедуру с вновь полученным деревом ранга .
При включении списка детей необходимо учесть возможность помеченности детей минимального узла. То есть уменьшить их ранг там, где это необходимо. Это требование вытекает из свойства 2 определения тонкого дерева. Очевидно, что для проверки помеченности узла требуется
операций.
В результате выполнения связывающих шагов получаем заполненный массив . Теперь остается только связать все деревья, находящиеся в этом массиве, в корневой список и найти в этом списке новый минимальный элемент. Очевидно, все это можно выполнить с трудоемкостью .
Чтобы оценить амортизационную стоимость операции , подсчитаем фактическую стоимость операции и изменение потенциала. Фактическая стоимость складывается из операций на проверку кучи на пустоту, действий при добавлении детей минимального узла в корневой список и (количество связывающих шагов) + при выполнении связывающих шагов.
В итоге фактическая стоимость операции удаления минимального элемента есть (количество связывающих шагов) + .
Очевидно, что потенциал уменьшился, как минимум, на число связывающих шагов, так как при каждом связывающем шаге количество деревьев в корневом списке уменьшается на единицу. Поскольку амортизационная стоимость равна фактической стоимости плюс изменение потенциала, то амортизационная стоимость равна .
Операция DecreaseKey . При уменьшении ключа у некорневого элемента
в куче на величину может быть нарушено свойство кучеобразности. Для восстановления этого свойства перемещаем поддерево с корнем в изменяемом элементе в корневой список, но при этом, возможно, оставшееся после переноса дерево может не оказаться тонким.
Покажем, как, затратив амортизированного времени, исправлять его структуру. В процедуре после уменьшения ключа корректируется, если это необходимо, указатель на минимальный элемент кучи. После этого проверяется, не является ли измененный узел корнем дерева . Если это действительно так, то процедура завершается, в противном случае переносим поддерево с корнем в узле в корневой список кучи и запускаем процедуру коррекции оставшегося дерева .
Будем различать два вида нарушений свойств тонкого дерева:
- Братские нарушения — это нарушения третьего правила из определения тонкого дерева.
- Родительские нарушения — это нарушения первого или второго правила.
Рассмотрим подробнее каждое из двух видов нарушений. Назовем узел
узлом локализации братского нарушения среди детей узла , если ранг узла отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1. Пример — на рис. 8.3.
Рис. 8.3.
Назовем узел узлом локализации родительского нарушения, если выполнено одно из трех условий:
- Ранг узла на три больше, чем ранг его самого левого сына.
- Ранг узла равен двум, и он не имеет детей.
- Узел есть помеченный корень дерева.
Пример приведен на рис. 8.4.
Рис. 8.4.
Рассмотрим теперь, как можно перестроить дерево, чтобы избавиться от братского нарушения либо свести его к родительскому. Пусть узел
— это узел локализации братского нарушения. Рассмотрим два возможных варианта.
Узел не помечен, то есть ранг его самого левого сына на единицу меньше ранга самого узла . Пример — на рис. 8.5.
Рис. 8.5.
В данном случае, чтобы исправить братское нарушение, помещаем на место пропущенного в братском списке поддерева поддерево с корнем в самом левом сыне узла . Узел при такой операции становится помеченным, но зато дерево теперь удовлетворяет всем трем свойствам определения тонкого дерева. Очевидно, что это операция заканчивает процедуру исправления дерева.
Узел помечен, тогда уменьшаем ранг узла на единицу. Это не исправит дерева, но зато теперь узлом локализации нарушения будет левый брат узла либо его родитель. В последней ситуации нарушение становится родительским. Пример приведен на рис. 8.6.
Рис. 8.6.
Таким образом, мы либо исправим структуру дерева, либо рекурсивно придем к узлу локализации родительского нарушения.
Выясним, чтo же делать с родительскими нарушениями. Пусть узел — это узел локализации родительского нарушения, а узел — родитель узла . Тогда предлагается переместить поддерево с корнем в узле в корневой список кучи, делая при этом узел
непомеченным. Считаем, что — это не корень дерева. Если узел не был помечен, то, очевидно, процедура исправления дерева закончена. Если он был помечен, то считаем его узлом локализации нового родительского нарушения. При этом, очевидно, количество помеченных узлов уменьшится на единицу. Продолжая такого вида рекурсивные шаги, мы либо дойдем до корня дерева, либо исправим его структуру раньше. Если узел стал корнем, то для того чтобы исправить структуру дерева, необходимо лишь сделать ранг корня на единицу большим ранга его самого левого сына. На этом процедура исправления дерева будет закончена.
Заметим, что каждый промежуточный шаг рекурсии уменьшает число помеченных узлов на единицу и добавляет в корневой список не более одного дерева. Тогда потенциал при каждом шаге рекурсии уменьшается как минимум на единицу. Отсюда и следует обещанная оценка времени выполнения операции .
Операция Delete(i,H) удаляет элемент из кучи
следующим образом. Ключ удаляемого элемента уменьшается до некоторого значения, меньше минимального, и элемент удаляется как минимальный. Очевидно, что трудоемкость этой операции есть .
Итак, амортизационная трудоемкость выполнения операций\linebreak и на тонкой куче из элементов равна , а для остальных операций, как было показано ранее, — .
<
