堆算法

MSTL堆算法的实现 更多...

函数
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 Iterator	is_heap_until (Iterator first, Iterator last, Compare comp)
	查找堆中破坏堆性质的首个元素
template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 Iterator	is_heap_until (Iterator first, Iterator last)
	查找堆中破坏堆性质的首个元素
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 bool	is_heap (Iterator first, Iterator last, Compare comp)
	检查范围是否为有效堆
template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 bool	is_heap (Iterator first, Iterator last)
	检查范围是否为有效堆
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	push_heap (Iterator first, Iterator last, Compare comp)
	向堆中插入元素
template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	push_heap (Iterator first, Iterator last)
	向堆中插入元素
template<typename Iterator, typename Distance, typename T, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	adjust_heap (Iterator first, Distance hole_index, Distance len, T value, Compare comp)
	堆调整辅助函数
template<typename Iterator, typename Distance, typename T, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	adjust_heap (Iterator first, Distance hole_index, Distance len, T value)
	堆调整辅助函数
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	pop_heap (Iterator first, Iterator last, Compare comp)
	删除堆顶元素
template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	pop_heap (Iterator first, Iterator last)
	删除堆顶元素
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	sort_heap (Iterator first, Iterator last, Compare comp)
	将堆转换为有序序列
template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	sort_heap (Iterator first, Iterator last)
	将堆转换为有序序列
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	make_heap (Iterator first, Iterator last, Compare comp)
	创建堆
template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
MSTL_CONSTEXPR20 void	make_heap (Iterator first, Iterator last)
	创建堆

详细描述

MSTL堆算法的实现

函数说明

adjust_heap()

template<typename Iterator, typename Distance, typename T, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 void adjust_heap	(	Iterator	first,
		Distance	hole_index,
		Distance	len,
		T	value,
		Compare	comp )

堆调整辅助函数

模板参数

Iterator	随机访问迭代器类型
Distance	距离类型
T	元素值类型
Compare	比较函数类型

参数

first	堆起始迭代器
hole_index	空洞位置索引
len	堆长度
value	要调整的值
comp	比较函数对象

在指定位置向下调整堆，然后在调整后的位置向上调整。 用于删除堆顶元素后的堆调整。

在文件 heap.hpp 第 173 行定义.

引用了 _INNER.

被这些函数引用 adjust_heap(), make_heap() , 以及 partial_sort_copy().

is_heap() [1/2]

template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 bool is_heap	(	Iterator	first,
		Iterator	last )

检查范围是否为有效堆

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始迭代器
last	范围结束迭代器

返回

如果范围是有效堆则返回 true，否则返回 false

在文件 heap.hpp 第 84 行定义.

引用了 _MSTL , 以及 is_heap_until().

is_heap() [2/2]

template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 bool is_heap	(	Iterator	first,
		Iterator	last,
		Compare	comp )

检查范围是否为有效堆

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始迭代器
last	范围结束迭代器
comp	比较函数对象

返回

如果范围是有效堆则返回 true，否则返回 false

在文件 heap.hpp 第 72 行定义.

引用了 _MSTL , 以及 is_heap_until().

is_heap_until() [1/2]

template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 Iterator is_heap_until	(	Iterator	first,
		Iterator	last )

查找堆中破坏堆性质的首个元素

模板参数

Iterator

随机访问迭代器类型

参数

first	堆起始迭代器
last	堆结束迭代器

返回

破坏堆性质的第一个元素的迭代器，如果范围是有效堆则返回 last

默认使用小于比较，创建最大堆。

在文件 heap.hpp 第 58 行定义.

引用了 _MSTL , 以及 is_heap_until().

is_heap_until() [2/2]

template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 Iterator is_heap_until	(	Iterator	first,
		Iterator	last,
		Compare	comp )

查找堆中破坏堆性质的首个元素

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	堆起始迭代器
last	堆结束迭代器
comp	比较函数对象

返回

破坏堆性质的第一个元素的迭代器，如果范围是有效堆则返回 last

检查范围 [first, last) 是否满足堆性质，返回第一个破坏堆性质的元素。 堆性质：

• 对于最大堆，父节点不小于子节点；
• 对于最小堆，父节点不大于子节点。

在文件 heap.hpp 第 36 行定义.

被这些函数引用 is_heap(), is_heap() , 以及 is_heap_until().

make_heap()

template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 void make_heap	(	Iterator	first,
		Iterator	last,
		Compare	comp )

创建堆

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始迭代器
last	范围结束迭代器
comp	比较函数对象

将范围 [first, last) 重新排列，使其满足堆性质。 从最后一个非叶子节点开始，向前调整每个节点。

在文件 heap.hpp 第 299 行定义.

引用了 _MSTL , 以及 adjust_heap().

被这些函数引用 make_heap(), partial_sort() , 以及 partial_sort_copy().

pop_heap()

template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 void pop_heap	(	Iterator	first,
		Iterator	last,
		Compare	comp )

删除堆顶元素

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	堆起始迭代器
last	堆结束迭代器
comp	比较函数对象

将堆的最大（或最小）元素移动到 last-1 位置， 并使范围 [first, last-1) 成为有效堆。

在文件 heap.hpp 第 247 行定义.

引用了 _INNER.

被这些函数引用 pop_heap() , 以及 sort_heap().

push_heap()

template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 void push_heap	(	Iterator	first,
		Iterator	last,
		Compare	comp )

向堆中插入元素

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	堆起始迭代器
last	堆结束迭代器
comp	比较函数对象

假设范围 [first, last-1) 是有效堆，将 *(last-1) 插入堆中。 调用后范围 [first, last) 是有效堆。

在文件 heap.hpp 第 142 行定义.

引用了 _INNER.

被这些函数引用 push_heap().

sort_heap()

template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

MSTL_CONSTEXPR20 void sort_heap	(	Iterator	first,
		Iterator	last,
		Compare	comp )

将堆转换为有序序列

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	堆起始迭代器
last	堆结束迭代器
comp	比较函数对象

通过反复弹出堆顶元素，将堆转换为升序（或降序）序列。 操作后，范围 [first, last) 不再满足堆性质，而是已排序。

在文件 heap.hpp 第 273 行定义.

引用了 _MSTL , 以及 pop_heap().

被这些函数引用 partial_sort(), partial_sort_copy() , 以及 sort_heap().