Структуры данных и модели вычислений
Реализация основных операций и оценки трудоемкости
Сосредоточим внимание на амортизационных оценках трудоемкости. Будем получать их методом потенциалов. Потенциалом тонкой кучи будем считать величину , где — количество деревьев в куче, а — число помеченных вершин. Заметим, что потенциал кучи неотрицателен и в начальный момент равен .
Операция MakeHeap. Эта операция создает указатель на новую пустую кучу. Очевидно, фактическая стоимость операции есть , а потенциал созданной кучи равен .
Операция FindMin (H). Указатель на узел с минимальным ключом в куче определяется с помощью указателя . Если куча пуста, то результирующий указатель нулевой. Амортизационная оценка совпадает с фактической и равна , потенциал не изменяется.
Операция Insert(i,H). С помощью этой операции осуществляется вставка в кучу нового элемента с ключом . При ее реализации создается новое тонкое дерево ранга , которое вставляется в корневой список кучи , разрывая его в произвольном месте. При необходимости перевычисляется ссылка на минимальный элемент.
Операция увеличивает потенциал на , так как добавляется одно дерево в корневой список кучи, но это не влияет на амортизационную оценку, которая равна фактической .
Операция Meld(H1, H2). Результатом этой операции является указатель на кучу, полученную слиянием двух куч
и . Она осуществляется соединением корневых списков сливаемых куч. При таком способе выполнения операции, как и при реализации вставки элемента в кучу, можем получить в корневом списке результирующей кучи несколько деревьев одинакового ранга. При удобном случае, а именно при удалении минимального элемента, мы освободим корневой список от этой неоднозначности. Оценка совпадает с оценками для всех предыдущих операций. Суммарный потенциал не изменяется.
