Определение кучи
Итак, во всех простых решениях по крайней мере одна из операций выполняется за время O(n) — это намного больше времени O(log n), на которое мы надеялись. На помощь приходит куча — структура данных, в нашем контексте сочетающая преимущества сортированного массива и списка.
Другими словами, Порядок кучи: для каждого элемента v в узле i элемент w родителя i удовлетворяет условию key(w) ≤ key(v).
Стрелками обозначены дочерние узлы трех верхних узлов дерева Прежде чем обсуждать работу с кучей, следует определиться со структурой данных, которая будет использоваться для ее представления. Можно использовать указатели: каждый узел содержит элемент, его ключ и три указателя (два дочерних узла и родительский узел).
Однако если заранее известна граница N общего коли- чества элементов, находящихся в куче в любой момент времени, можно обойтись и без указателей. Такие кучи могут храниться в массиве H с индексами i = 1, …, N. Узлы кучи соответствуют позициям в массиве.
H[1] представляет собой корневой узел, а для любого узла в позиции i его дочерние узлы находятся в позициях leftChild(i) = 2i и rightChild(i) = 2i + 1. Таким образом, два дочерних узла корня находятся в позициях 2 и 3, а родитель узла в позиции i находится в позиции parent(i) = .
Если куча в какой-то момент содержит n < N элементов, то первые n позиций массива используются для хранения n элементов кучи, а количество элементов в H обозначается length(H).
С таким представлением куча в любой мо- мент времени является сбалансированной. В правой части рис. 2.3 показано пред- ставление в виде массива для кучи, изображенной в левой части.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу