Data Structures . Boost , The Boost C++ Libraries BoostBook Documentation Subset , Chapter 15. Boost.Heap

Data Structures

Data Structure Configuration

boost.heap предоставляет следующие структуры данных:

boost::heap::priority_queue

Класс priority_queue является оберткой к куче функций stl. Он реализует кучу в качестве адаптера контейнера на вершине std::vector и является неизменным.

boost::heap::d_ary_heap

D-ary heaps представляют собой обобщение бинарной кучи с каждым нелистовым узлом, имеющим N детей. Для низкой проходимости высота кучи больше, но количество сравнений для поиска самого большого узла ребенка больше. Груды D-ary реализованы в виде контейнерных адаптеров на основе std::vector.

Структура данных может быть сконфигурирована как изменчивая. Это достигается путем хранения значений внутри std::list.

boost::heap::binomial_heap

Биномиальные кучи представляют собой кучи узловой базы, которые реализуются как набор биномиальных деревьев разного порядка. Наиболее важные операции кучи имеют наихудшую сложность O(log n). В отличие от d-ary heaps, биномиальные кучи также могут быть объединены в O(log n).

boost::heap::fibonacci_heap

Груды Фибоначчи представляют собой кучи узловых оснований, которые реализуются как лес кучных деревьев. Они обеспечивают лучшую амортизированную производительность, чем биномиальные кучи. За исключением pop() и erase(), наиболее важные операции кучи имеют постоянную амортизированную сложность.

boost::heap::pairing_heap

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

Pettie, Seth (2005), "Towards the final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174–183

boost::heap::skew_heap

Skew heaps являются саморегулирующимися узлами на основе кучи. Хотя для структуры дерева нет ограничений, все операции с кучей могут выполняться в O(log n).

Table 15.1. Comparison of amortized complexity

	`top()`	`push()`	`pop()`	`обновление()`	`увеличение()`	`снижение()`	`erase()`	`merge_and_clear()`
`boost::heap::priority_queue`	`O(1)`	O(log(N))	O(log(N))	n/a	n/a	n/a	n/a	O((N+M)*log(N+M))
`boost::heap::d_ary_heap`	`O(1)`	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O((N+M)*log(N+M))
`boost::heap::binomial_heap`	`O(1)`	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N+M))
`boost::heap::fibonacci_heap`	`O(1)`	O(1)	O(log(N))	O(log(N)) ^[a]	O(1)	O(log(N))	O(log(N))	O(1)
`boost::heap::pairing_heap`	`O(1)`	O(2*2log(log(N)))	O(log(N))	O(2*2log(log(N)))	O(2*2log(log(N)))	O(2*2log(log(N)))	O(2*2log(log(N)))	O(2*2log(log(N)))
`boost::heap::skew_heap`	`O(1)`	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N))	O(log(N+M))
^[a] Метод фибоначчи `update_lazy()`, который также имеет амортизированную сложность O(log(N)), но не пытается консолидировать внутренний лес

Data Structure Configuration

Структуры данных могут быть сконфигурированы с помощью шаблонов в стиле Boost.Parameter.

boost::heap::compare: Предикат для определения порядка кучи, необязательный (по умолчанию boost::heap::compare >)
boost::heap::allocator: Распределитель для управления внутренней памятью, необязательный (по умолчанию boost::heap::allocator >)
boost::heap::stable: Настраивает кучу для использования порядка стабильной кучи , необязательно (по умолчанию boost::heap::stable).
boost::heap::mutable_: Конфигурирует кучу, чтобы она была изменчивой. boost::heap::d_ary_heap и boost::heap::skew_heap должны быть настроены с помощью этой политики, чтобы включить интерфейс mutability.
boost::heap::stability_counter_type: Конфигурирует целочисленный тип, используемый для счетчика стабильности, необязательно (по умолчанию boost::heap::stability_counter_type). Для получения более подробной информации обратитесь к разделу Стабильность .
boost::heap::constant_time_size: Указывает, должен ли size() иметь линейную или постоянную сложность. Этот аргумент доступен только для структур данных, основанных на узлах, и если он доступен, он необязателен (по умолчанию boost::heap::constant_time_size )
boost::heap::arity: Определяет популяцию д-рая кучи. Для получения подробной информации, пожалуйста, обратитесь к ссылке класса boost::heap::d_ary_heap
boost::heap::store_parent_pointer: Храните родительский указатель в куче узлов. Эта политика доступна только в boost::heap::skew_heap.

Статья Data Structures раздела The Boost C++ Libraries BoostBook Documentation Subset Chapter 15. Boost.Heap может быть полезна для разработчиков на c++ и boost.