Boost C++ 库

typedef implementation_defined::iterator iterator;

**注意：** 迭代器不会按照优先级顺序遍历优先级队列。

explicit pairing_heap(value_compare const & cmp = value_compare());

**效果：** 构造一个空的优先级队列。

**复杂度：** 常数。

explicit pairing_heap(allocator_type const & alloc);

**效果：** 构造一个空的优先级队列。

**复杂度：** 常数。

pairing_heap(pairing_heap const & rhs);

**效果：** 从 rhs 复制构造优先级队列。

**复杂度：** 线性。

pairing_heap(pairing_heap && rhs);

**效果：** C++11 风格的移动构造函数。

**复杂度：** 常数。

**注意：** 仅在未定义 BOOST_NO_CXX11_RVALUE_REFERENCES 时可用。

pairing_heap & operator=(pairing_heap && rhs);

**效果：** C++11 风格的移动赋值运算符。

**复杂度：** 常数。

**注意：** 仅在未定义 BOOST_NO_CXX11_RVALUE_REFERENCES 时可用。

pairing_heap & operator=(pairing_heap const & rhs);

**效果：** 从 rhs 为优先级队列赋值。

**复杂度：** 线性。

~pairing_heap(void);

bool empty(void) const;

**效果：** 如果优先级队列不包含任何元素，则返回 true。

**复杂度：** 常数。

size_type size(void) const;

**效果：** 返回优先级队列中包含的元素数。

**复杂度：** 如果使用 constant_time_size<true> 配置，则为常数，否则为线性。

size_type max_size(void) const;

**效果：** 返回优先级队列可以包含的最大元素数。

**复杂度：** 常数。

void clear(void);

**效果：** 从优先级队列中移除所有元素。

**复杂度：** 线性。

allocator_type get_allocator(void) const;

**效果：** 返回分配器。

**复杂度：** 常数。

void swap(pairing_heap & rhs);

**效果：** 交换两个优先级队列。

**复杂度：** 常数。

const_reference top(void) const;

**效果：** 返回对最大元素的 const_reference。

**复杂度：** 常数。

handle_type push(value_type const & v);

**效果：** 向优先级队列添加一个新元素。返回元素的句柄。 **复杂度：** 2**2*log(log(N)) (摊销)。

template<class... Args> handle_type emplace(Args &&... args);

**效果：** 向优先级队列添加一个新元素。 元素直接原地构造。返回元素的句柄。 **复杂度：** 2**2*log(log(N)) (摊销)。

void pop(void);

**效果：** 从优先级队列中移除顶部元素。

**复杂度：** 对数 (摊销)。

void update(handle_type handle, const_reference v);

**效果：** 将 v 赋值给 handle 处理的元素并更新优先级队列。 **复杂度：** 2**2*log(log(N)) (摊销)。

void update(handle_type handle);

**效果：** 在 handle 处理的元素更改后更新堆。 **复杂度：** 2**2*log(log(N)) (摊销)。

**注意：** 如果未调用此函数，则在句柄更新后，数据结构的行为未定义！

void increase(handle_type handle, const_reference v);

**效果：** 将 v 赋值给 handle 处理的元素并更新优先级队列。 **复杂度：** 2**2*log(log(N)) (摊销)。

**注意：** 新值应大于当前值。

void increase(handle_type handle);

**效果：** 在 handle 处理的元素更改后更新堆。 **复杂度：** 2**2*log(log(N)) (摊销)。

**注意：** 如果未调用此函数，则在句柄更新后，数据结构的行为未定义！

void decrease(handle_type handle, const_reference v);

**效果：** 将 v 赋值给 handle 处理的元素并更新优先级队列。 **复杂度：** 2**2*log(log(N)) (摊销)。

**注意：** 新值应小于当前值。

void decrease(handle_type handle);

**效果：** 在 handle 处理的元素更改后更新堆。 **复杂度：** 2**2*log(log(N)) (摊销)。

**注意：** 新值应小于当前值。 如果未调用此函数，则在句柄更新后，数据结构的行为未定义！

void erase(handle_type handle);

**效果：** 从优先级队列中移除 handle 处理的元素。 **复杂度：** 2**2*log(log(N)) (摊销)。

iterator begin(void) const;

**效果：** 返回指向优先级队列中第一个元素的迭代器。

**复杂度：** 常数。

iterator end(void) const;

**效果：** 返回指向优先级队列末尾的迭代器。

**复杂度：** 常数。

ordered_iterator ordered_begin(void) const;

**效果：** 返回指向优先级队列中第一个元素的有序迭代器。

**注意：** 有序迭代器按堆顺序遍历优先级队列。

ordered_iterator ordered_end(void) const;

**效果：** 返回指向优先级队列中第一个元素的有序迭代器。

**注意：** 有序迭代器按堆顺序遍历优先级队列。

void merge(pairing_heap & rhs);

**效果：** 将 rhs 中的所有元素合并到此队列中。 **复杂度：** 2**2*log(log(N)) (摊销)。

value_compare const & value_comp(void) const;

**效果：** 返回优先级队列使用的 value_compare 对象。

template<typename HeapType> bool operator<(HeapType const & rhs) const;

**返回值：** 堆数据结构的逐元素比较结果。

**要求：** 两个堆的 value_compare 对象必须匹配。

template<typename HeapType> bool operator>(HeapType const & rhs) const;

**返回值：** 堆数据结构的逐元素比较结果。

**要求：** 两个堆的 value_compare 对象必须匹配。

template<typename HeapType> bool operator>=(HeapType const & rhs) const;

**返回值：** 堆数据结构的逐元素比较结果。

**要求：** 两个堆的 value_compare 对象必须匹配。

template<typename HeapType> bool operator<=(HeapType const & rhs) const;

**返回值：** 堆数据结构的逐元素比较结果。

**要求：** 两个堆的 value_compare 对象必须匹配。

template<typename HeapType> bool operator==(HeapType const & rhs) const;

**要求：** 两个堆的 value_compare 对象必须匹配。

template<typename HeapType> bool operator!=(HeapType const & rhs) const;

**要求：** 两个堆的 value_compare 对象必须匹配。

static handle_type s_handle_from_iterator(iterator const & it);