36. Бинарная куча. Добавление элемента.

Бинарной (двоичной) кучей (binary heap) называется массив, обладающей определенными свойствами упорядоченности.

для которого выполнены три условия:

1. Значение в любой вершине не меньше, чем значения её потомков.

2. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.

3. Последний слой заполняется слева направо

4. Каждая вершина содержит ключ и информацию

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служит процедура Heapify. Она восстанавливает свойство кучи в дереве, у которого левое и правое поддеревья удовлетворяют ему. Эта процедура принимает на вход массив элементов A и индекс i. Она восстанавливает свойство упорядоченности во всём поддереве, корнем которого является элемент A[i].

Добавление элементаInsertHeap:

1. Увеличить на один размер кучи

2. Поместить новый элемент за последним элементом кучи

3. Дать всплыть элементу до своего уровня

Временная сложность алгоритма O(log₂N) – глубина дерева

void Heap::Insert(void* x)

{

int i;

if(!isFull())

{

Storage[i=++Size-1]=x;

while(i>0&&isLess(Storage[Parent(i)],Storage[i]))

{

Swap(Parent(i),i);

i=Parent(i);

}

}

elsethrow (ExcFull)INSERT;

}

37. Обзор куч: левосторонние, биномиальные, фибоначевы, тонкие. Оценка сложности. Бинарной (двоичной) кучей (binary heap) называется массив, обладающей определенными свойствами упорядоченности. Для него выполняются три условия:1)Значение в любой вершине не меньше, чем значения её потомков.2)Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.3)Последний слой заполняется слева направо.4)Каждая вершина содержит ключ и информацию. Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служит процедура Heapify. Она восстанавливает свойство кучи в дереве, у которого левое и правое поддеревья удовлетворяют ему. Эта процедура принимает на вход массив элементов A и индекс i. Она восстанавливает свойство упорядоченности во всём поддереве, корнем которого является элемент A[i]. Левосторонняя куча — бинарное дерево, для каждого узла которого ранг его левого непосредственного потомка в расширенном дереве не меньше ранга его правого потомка. Ранг узла - уменьшенное на 1 расстояние (число ребер) от него до ближайшего неполного потомка. Свойства левостороннего дерева: Правая ветвь из любого узла дерева имеет минимальную длину среди всех ветвей, исходящих из этого узла. Длина правой ветви левостороннего дерева, имеющего N узлов ограничена c[log2N]. Node = element, key, rank, left, right, parent. Биноминальные деревья:1)B0 — дерево, состоящее из одного узла высоты 0; 2)Bk - дерево высотыk формируется из двух деревьев Bk-1 , при этом корень одного из них становится потомком корня другого. Биномиальный лес — это набор биномиальных деревьев, в котором любые два дерева имеют разные высоты. Фибоначчиевы кучи:1)время работы всех операций не требующих удаления- равно O(1);2)удаление O(logn).Название рассматриваемых куч связано с использованием чисел Фибоначчи при анализе трудоемкости выполнения операций. В отличие от биномиальных куч, в которых операции вставки, поиска элемента с минимальным ключом, удаления, уменьшения ключа и слияния выполняются за время O(logn), в фибоначчиевых кучах они выполняются более эффективно. Операции, не требующие удаления элементов, в этих кучах имеют учетную стоимость O(1). Теоретически фибоначчиевы кучи особенно полезны, если число операций удаления мало по сравнению с остальными операциями. Такая ситуация возникает во многих приложениях. При отсутствии операций уменьшения ключа и удаления элемента фибоначчиевы кучи имели бы ту же структуру, что и биномиальные. Строение фибоначчиевой кучи. Каждая фибоначчиева куча состоит из нескольких деревьев. В отличие от биномиальных деревьев, здесь дети любого узла могут записываться в любом порядке. Они связываются в двусторонний циклический список. Каждый узел xэтого списка имеет поляleft[x] и right[x], указывающие на его соседей в списке. Тонкие кучи аналогичны биномиальным кучам.

Операция Двоичная Биномиальная Фибоначчиева

найти минимум Θ(1) Θ(log n) or Θ(1) Θ(1)

удалить минимум Θ(log n) Θ(log n) O(log n)

добавить Θ(log n) O(log n) Θ(1)

уменьшить ключ Θ(log n) Θ(log n) Θ(1)

слияние Θ(n) O(log n)** Θ(1)

38. Хэш-таблицы.Понятие, назначение и принцип организации.

Сочетание массивов и списков с небольшой добавкой математики пример- записная книжка.

[_____]→[date|____]→[date|____]→[date|NULL]

[NULL]

[NULL]

[_____]→[date|NULL]

[NULL]

Понятие:

• хэш-таблица — это динамическое множество, поддерживающее словарные операции: добавление, поиск и удаление элемента, использующее специальные методы адресации. Основное отличие таблиц от других динамических множеств – вычисление адреса элемента по значению ключа.

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

Назначение:

• символьная таблица – словарь

• базах данных

• компилятор для управления информацией о переменных, ассемблер

• Web-браузер для хранения адресов страниц, (cache — кэширования) недавно использованных доменных имен и их IP-адресов.

Основное назначение хеш-функции поставить в соответствие различным ключам по возможности разные не отрицательные целые числа.

Если разным значениям ключей таблицы хеш-функция генерирует одинаковые адреса, то говорят, что возникает коллизия.

Организация: прямая и открытая адресация

Если разным значениям ключей таблицы хеш-функция генерирует одинаковые адреса, то говорят, что возникает коллизия.

При прямой адресации строится для каждого адреса таблицы H связный список элементов, ключи которых отображаются на этот адрес. Коллизия разрешается с помощью цепочек. В строке таблицы Hс номером jхранится не сам элемент, а указатель на голову списка тех элементов, у которых хэш-значение ключа равно j, если нет то – NULL. Хэш-таблица может быть представлена массивом списков.

При открытой адресации все записи хранятся в самой хэш-таблице(хэш-списков нет), каждая ячейка содержит значение либо NULL.