- •Кучи (heap )
- •Область использования
- •Бинарная куча (binary heap)
- •Сортирующее дерево
- •Бинарная куча, состоящая из 10
- •каждая вершина: ►ключ (key) ►информационное поле
- •Основное свойство кучи
- •Свойства
- •Основные операции
- •Процедура Heapify
- •Процедура BuildHeap
- •Процедура SortHeap
- •Процедура ExtractMax
- •Процедура InsertHeap
- •Определение родительской вершины
- •Определение левой дочерней вершины
- •Определение правой дочерней вершины
- •Левосторонние кучи
- •Свойства левостороннего дерева
- •Самоорганизующаяся куча
- •Биномиальное дерево
- •Свойства биномиальных деревьев
- •Биномиальная куча
- •Фибоначчиева куча (англ. Fibonacci heap)
- •набор деревьев
- •►Дочерние узлы x объединены при помощи указателей left и right в один циклический
Процедура BuildHeap
►Номер первой вершины в последовательности [(N-1)/2].
►Временная сложность данного
алгоритма T(N) = [(N-1)/2]* TH(N), где TH(N) = O(log2N)
►T(N)= O(N*log2N)
Процедура SortHeap
►1) выпонить процедуру BuildHeap;
►2) обменять местами элементы A[0] и A[N-1];
►3) уменьшить размер кучи на единицу:
►4) выполнить процедуру Heapify для элемента 0.
►Сложность T(N) = O(N) + O(N*log2N) +(N-
1)*O(i))= O(N) + O(N*log2N) + O(N )= O(Nlog2N)
Процедура ExtractMax
►1) сохранить значение элемента A[0] в промежуточной памяти;
►2) записать значение последнего элемента кучи A[N-1] в A[0];
►3)уменьшить на единицу размер кучи;
► 4) выпонить процедуру Heapify для элемента 0.
► T(N)=O(log2N)+O(i) = O(log2N)
Процедура InsertHeap
►1) увеличить размер кучи на один;
►2) поместить новый элемент за последним элементом кучи;
►3) дать всплыть этому элементу до своего
уровня.
► T(N) = O(N)
Определение родительской вершины
Определение левой дочерней вершины
Определение правой дочерней вершины
Левосторонние кучи
►Левосторонняя куча — бинарное дерево, для каждого узла которого ранг его левого непосредственного потомка в расширенном дереве не меньше ранга его правого потомка.
►Рангузла - уменьшенное на 1 расстояние (число ребер) от него до ближайшего неполного потомка.
Свойства левостороннего дерева
►Правая ветвь из любого узла дерева имеет минимальную длину среди всех ветвей, исходящих из этого узла.
►Длина правой ветви левостороннего дерева, имеющего N узлов, ограничена c[log2N].
Самоорганизующаяся куча
► O(n), где n — число элементов в очереди.
►Cреднее время выполнения m произвольных операций есть O(mlog(n)), то есть время, приходящееся на одну операцию, равно O(log(n)).
►узлыпредставлять записями вида
►Nodem (element, key, left, right)
► Операции СЛИТЬ, ВСТАВИТЬ,
УДАЛИТЬ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ, НАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ