Двоичные кучи, основные операции и характеристики

Двоичная куча - такое двоичное дерево, для которого выполнены три условия:

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

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

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

Над кучей можно выполнять следующие операции:

· Добавить элемент в кучу. Сложность

· Исключить максимальный элемент из кучи. Время работы

· Изменить значение любого элемента. Время работы

На основе этих операций можно выполнять следующие действия:

· Превратить неупорядоченный массив элементов в кучу. Сложность

· Отсортировать массив путём превращения его в кучу, а кучи в отсортированный массив. Время работы

Здесь N — количество элементов кучи. Пространственная сложность — для всех вышеперечисленных операций и действий.

Хеш-таблицы, метод цепочек

Прямая адресация применяется для небольших множеств ключей. Требуется задать динамическое множество, каждый элемент которого имеет ключ из множества U = {0,1,..., m - 1}, где m не слишком велико, никакие два элемента не имеют одинаковых ключей.

Для представления динамического множества используется массив (таблицу с прямой адресацией), Т [0..m - 1], каждая позиция, или ячейка, которого соответствует ключу из пространства ключей U.

Ячейка k указывает на элемент множества с ключом k. Если множество не содержит элемента с ключом k, то Т [k] = NULL.

Операция поиска по ключу занимает время O(1)

Недостатки прямой адресации:

• если пространство ключей U велико, хранение таблицы Т размером |U| непрактично, а то и вовсе невозможно — в зависимости от количества доступной памяти и размера пространства ключей

• множество К реально сохраненных ключей может быть мало по сравнению с пространством ключей U, а в этом случае память, выделенная для таблицы Т, в основном расходуется напрасно.

Хеш-функция – такая функция h, которая определяет местоположение элементов множества U в таблице T.

При хешировании элемент с ключом k хранится в ячейке h(k), хеш-функция h используется для вычисления ячейки для данного ключа k. Функция h отображает пространство ключей U на ячейки хеш-таблицы Т [О..m - 1]:

h: U → {0,1,..., m -1}.

величина h (к) называется хеш-значением ключа к.

Когда множество К хранящихся в словаре ключей гораздо меньше пространства возможных ключей U, хеш-таблица требует существенно меньше места, чем таблица с прямой адресацией.

Цель хеш-функции состоит в том, чтобы уменьшить рабочий диапазон индексов массива, и вместо |U| значений можно обойтись всего лишь m значениями.

Требования к памяти могут быть снижены до θ(|К|), при этом время поиска элемента в хеш-таблице остается равным О(1) - это граница среднего времени поиска, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая.

Коллизия – ситуация, когда два ключа отображаются в одну и ту же ячейку.

Например, h(43) = h(89) = h(112) = k

Метод цепочек:

Идея: Хранить элементы множества с одинаковым значением хэш-функции в виде списка.

 

h(51) = h(49) = h(63) = i

Анализ

Наихудший случай: если хэш-функция для всех элементов множество выдает одно и то же значение. Время доступа равно Θ(n), при |U | = n.

Средний случай: для случая, когда значения хэш-функции равномерно распределены.

Каждый ключ с равной вероятностью может попасть в любою ячейку таблицы, вне зависимости от того куда попали другие ключи.

Пусть дана таблицы T[0..m - 1], и в ней хранится n ключей.

Тогда, а = n/m - среднее количество ключей в ячейках таблицы.

Время поиска отсутствующего элемента – Θ(1 + α).

Константное время на вычисления значения хэш-функции плюс время на проход списка до конца, т.к. средняя длина списка - α, то результат равен Θ(1) + Θ(α) = Θ(1 + α)

Если количество ячеек таблицы пропорционально количеству элементов, хранящихся в ней, то n = O(m) и, следовательно, α = n/m = O(m)/m = O(1), а значит поиск элемента в хэш-таблице в среднем требует времени Θ(1).

Операции

• вставка элемента в таблицу

• удаление

также требуют времени O(1)

Выбор хэш-функции

• Ключи должны равномерно распределятся по всем ячейкам

таблицы.

• Закономерность распределения ключей хэш-функции не должна коррелировать с закономерностями данных. (Например, данные – это четные числа).

Методы:

• Метод деления

• Метод умножения

 

Метод деления

h (k) = k mod m

Проблема маленького делителя m

Пример №1. m = 2 и все ключи четные Þ нечетные ячейки не

заполнены.

Пример №2. m = 2^r Þ хэш не зависит от бито в выше r.

Метод умножения

Пусть m = 2^r, ключи являются w-битными словами.

h(k) = (A • k mod 2^w) >> (w - r), где

A mod 2 = 1 ∩ 2^w-1 < A< 2^w

• He следует выбирать A близко к 2^w-1 и 2^w

• Данный метод быстрее метода деления

 

Метод умножения: пример

m = 8 = 2³, w = 7