RobbEr's Blog

Welcome

STL-priority_queue

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

简介

priority_queue 为优先队列，提供常数时间的最大元素查找，对数代价的插入与删除

其底层为heap实现，且可通过用户提供的Compare更改序列，如std::greater<T>可以使最小元素作为 top() 出现

priority_queue是容器适配器，无迭代器，不支持随机访问

类模板

其类模板相较于其他stl模板有些许不同

1
2
3
4
5
template<
    class T,        //数据类型
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

在参数2Container不输入时，默认容器为 vector ,但也支持 deque

Container也可使用 deque，因为 priority_queue 的底层容器必须支持随机访问迭代器，不能用list的原因也是如此，但是 priority_queue 不支持随机访问

参数3Compare不输入时，默认方法为std::less<T>,也就是max_heap，也可以使用std::greater指定为min_heap

成员函数

以下时间复杂度是以 vector 作为 Container时的

容量相关

  1. size() - 返回 priority_queue 中元素数 O(1)
  2. empty() - 当前 priority_queue 是否为空 O(1)

元素访问相关

  1. top() - 访问队头元素 O(1)

修改器相关

  1. push() - 插入元素，并对底层容器排序（底层算法为 push_heap算法） O(log2(n))
  2. pop() - 删除队头元素（底层为 pop_heap 算法） O(log2(n))
  3. swap() - 交换元素 (C++11)
  4. emplace() - 插入一个元素到 priority_queue，调用构造函数，并对底层容器排序 (C++11)

深入底层

下文转自Leiym Blog，有所删改

priority_queue 与 stack, queue 一样，只能算是适配器，而不能算是容器类

了解priority_queue前，需要先了解heap这个数据结构

heap

heap直译为堆，本质为完全二叉树，由完全二叉树的性质 （当用一个数组来从左到右，从上到下的顺序存放完全二叉树的元素时，一个元素位于 i 处时，其左子节点必位于 2i 处，其右子节点必位于 2i+1 处，其父节点必位于 i/2(取整) 处） 可得，可以使用数组来隐晦的表示 heap

并且由于 heap 插入与删除元素都有对数级的表现，并且由于其隐式表达的便捷性，用其作为 priority_queue 的底层容器性价比最高

并且为了可拓展的方便，priority_queue 的默认Container为 vector ,默认 Compare 为std::less，这里以max_heap为例（父节点键值比子节点键值大）

heap算法

用 vector 来表示heap时，需要有两个迭代器 first 和 last 来表示可操作范围，即在 first 和 last 之间为 heap 的元素

要弄清楚 priority queue 各个方法的底层实现时，必须先弄清楚 heap 的四个算法。

push_heap算法

目的：将一个新元素插入到已构建好的 heap 中

步骤：

  1. 将新加入的元素放在最下层，从左至右的第一个空缺叶节点处，使加入新元素后的树仍为完全二叉树
  2. 将新元素与其父节点比较键值大小，如果新元素大，则交换其与父节点的位置
  3. 重复第2步，直至新元素小于父节点或新元素已位于根节点处。（上溯）

时间复杂度：由于最坏情况是上溯到根节点，所以上溯次数最多是完全二叉树的深度，由完全二叉树的性质可得：其深度为 [log2n] + 1（向下取整），所以 push_heap 算法的时间复杂度为 O(log2n)

pop_heap算法

目的：将根节点取出树，并放置到 vector 可操作范围的最末端。

步骤：

  1. 将根节点取出，并将最后一个子节点放置到根节点位置， 称其为替补元素。 last 迭代器减一 ，然后将原来根节点的元素放置到 last 所指处。（本质是根节点与最后的子节点调换在 vector 中的位置）
  2. 将替补元素与其左右子节点中键值较大的一个做比较，如果替补元素键值小，则调换它们的位置
  3. 重复第二步，直至替补元素无子节点或键值大于其所有子节点。（下溯）
    hOJC36.md.jpg

时间复杂度：同 push_heap ,其最坏情况是下溯到最底层。所以其时间复杂度为 O(log2n)

sort_heap 算法

目的：利用 pop_heap 每次都将键值最大的元素放置到可操作范围最末端，得到从小到大的排序序列

步骤：

  1. 执行 pop_heap 算法
  2. 重复第一步，直至可操作范围为0，即所有元素均被取出。

时间复杂度：因为执行了 n 步 pop_head 算法，所以时间复杂度为 O(nlog2n)

make_heap 算法

目的：将一段现有的数据转化为 heap

步骤：

  1. 构建堆实质是一个不断调整子树，使得树满足堆的特性
  2. 调整以非叶结点为单位，顺序是从后往前。调整的步骤为：如果调整节点比其最大的子节点小，则调换它们的顺序，并对下一个非叶节点进行调整

时间复杂度：最坏的情况下需要遍历所有非叶节点才可以完成调整，非叶节点的个数为 n 数量级，所以时间复杂度为O(n)