类模板 pairing_heap

boost::heap::pairing_heap — 配对堆

概要

// In header: <boost/heap/pairing_heap.hpp>

template<typename T, class... Options> 
class pairing_heap {
public:
  // types
  typedef T                                        value_type;      
  typedef implementation_defined::size_type        size_type;       
  typedef implementation_defined::difference_type  difference_type; 
  typedef implementation_defined::value_compare    value_compare;   
  typedef implementation_defined::allocator_type   allocator_type;  
  typedef implementation_defined::reference        reference;       
  typedef implementation_defined::const_reference  const_reference; 
  typedef implementation_defined::pointer          pointer;         
  typedef implementation_defined::const_pointer    const_pointer;   
  typedef implementation_defined::iterator         iterator;        
  typedef implementation_defined::const_iterator   const_iterator;  
  typedef implementation_defined::ordered_iterator ordered_iterator;
  typedef implementation_defined::handle_type      handle_type;     

  // public member functions
  explicit pairing_heap(value_compare const & = value_compare());
  explicit pairing_heap(allocator_type const &);
  pairing_heap(pairing_heap const &);
  pairing_heap(pairing_heap &&);
  pairing_heap & operator=(pairing_heap &&);
  pairing_heap & operator=(pairing_heap const &);
  ~pairing_heap(void);
  bool empty(void) const;
  size_type size(void) const;
  size_type max_size(void) const;
  void clear(void);
  allocator_type get_allocator(void) const;
  void swap(pairing_heap &);
  const_reference top(void) const;
  handle_type push(value_type const &);
  template<class... Args> handle_type emplace(Args &&...);
  void pop(void);
  void update(handle_type, const_reference);
  void update(handle_type);
  void increase(handle_type, const_reference);
  void increase(handle_type);
  void decrease(handle_type, const_reference);
  void decrease(handle_type);
  void erase(handle_type);
  iterator begin(void) const;
  iterator end(void) const;
  ordered_iterator ordered_begin(void) const;
  ordered_iterator ordered_end(void) const;
  void merge(pairing_heap &);
  value_compare const & value_comp(void) const;
  template<typename HeapType> bool operator<(HeapType const &) const;
  template<typename HeapType> bool operator>(HeapType const &) const;
  template<typename HeapType> bool operator>=(HeapType const &) const;
  template<typename HeapType> bool operator<=(HeapType const &) const;
  template<typename HeapType> bool operator==(HeapType const &) const;
  template<typename HeapType> bool operator!=(HeapType const &) const;

  // public static functions
  static handle_type s_handle_from_iterator(iterator const &);

  // public data members
  static const bool constant_time_size;
  static const bool has_ordered_iterators;
  static const bool is_mergable;
  static const bool is_stable;
  static const bool has_reserve;
};

描述

配对堆是自调整二叉堆。虽然设计和实现相当简单，但其复杂度分析仍未解决。详情请参考

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

模板参数 T 是容器管理的类型。用户可以指定其他选项，如果未提供选项，则使用默认选项。

容器支持以下选项

boost::heap::compare<>, 默认为 compare<std::less<T> >
boost::heap::stable<>, 默认为 stable<false>
boost::heap::stability_counter_type<>, 默认为 stability_counter_type<boost::uintmax_t>
boost::heap::allocator<>, 默认为 allocator<std::allocator<T> >
boost::heap::constant_time_size<>, 默认为 constant_time_size<true>

`pairing_heap` 公有类型

typedef implementation_defined::iterator iterator;

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

`pairing_heap` 公有成员函数

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 风格的移动构造函数。

复杂度： 常数时间。
```
pairing_heap & operator=(pairing_heap && rhs);
```
效果： C++11 风格的移动赋值。

复杂度： 常数时间。
```
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;
```
效果： 返回对最大元素的常量引用。

复杂度： 常数时间。
```
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;
```
等价比较 返回： 如果两个堆数据结构等价，则返回 True。
要求： 两个堆的 value_compare 对象必须匹配。
```
template<typename HeapType> bool operator!=(HeapType const & rhs) const;
```
等价比较 返回： 如果两个堆数据结构不等价，则返回 True。
要求： 两个堆的 value_compare 对象必须匹配。

`pairing_heap` 公有静态函数

static handle_type s_handle_from_iterator(iterator const & it);

Boost C++ 库

类模板 pairing_heap

概要

描述

pairing_heap 公有类型

pairing_heap 公有成员函数

pairing_heap 公有静态函数

`pairing_heap` 公有类型

`pairing_heap` 公有成员函数

`pairing_heap` 公有静态函数