C++ priority_queue 的使用和源码详解

admin管理员组

文章数量:1623791

目录

简介

priority_queue 的使用

泛型算法make_heap()、push_heap()、pop_heap()

make_heap()

push_heap()

pop_heap()

---

简介

priority_queue 是一个拥有权值观念的 queue，它允许加入新的元素、移除旧的元素、查看 priority_queue 中权值之最的元素等功能。priority_queue 只允许在底端加入元素，并从顶端取出元素，除此之外没有其它存取元素的途径。

priority_queue 提供常数时间的最大元素(默认)查找，对数代价的插入与释放。可为用户提供的 compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

虽然priority_queue 的名字中带有 queue，但是其底层的逻辑结构是堆。缺省情况下 priority_queue 利用一个大顶堆完成(底层存储结构是 vector)。堆结构能满足 priority_queue 所需要的”按照权值高低自动排序”的特性。这里要弄清楚的一点是：priority_queue 底层缺省使用 vector存 储数据，这是它的存储结构。而在逻辑上，它将序列视为一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的关系，在当前无序区间中选择关键字最大(或最小)的元素。

关于堆的数据结构，可以看这篇博客：通俗易懂的讲解堆排序(含Gif图)

priority_queue 的所有元素，进出都有一定的规则，只有其顶端的元素，才有机会被外界取用。同时，priority_queue 不提供遍历功能，也没有迭代器。由于 priority_queue 完全以底部容器为根据(被归类为容器适配器)，再加上 heap 处理规则，所以实现非常简单。STL 源码很简短，此处完整列出：

template < class T, class Sequence = vector<T>, 
		   class Compare = less<typename Sequence::value_type> >
class priority_queue {
public:
	typedef typename Sequence::value_type value_type;
	typedef typename Sequence::size_type size_type;
	typedef typename Sequence::reference reference;
	typedef typename Sequence::const_reference const_reference;
protected:
	Sequence c;        //底层容器
	Compare comp;      //元素大小比较
public:
	priority_queue() : c() {}
	explicit priority_queue(const Compare& x) : c(), comp(x) {}
	
	//以下用到的 make_heap(), push_heap(), pop_heap() 都是泛型算法
	//任意一个构造函数都立刻于底层容器内产生一个 implicit representation heap
	template <class InputIterator>
	priority_queue(InputIterator first, InputIterator last, const Compare& x)　: c(first, last), comp(x) 
	{ make_heap( c.begin(), c.end(), comp); }
	
	template <class InputIterator>
	priority_queue(InputIterator first, InputIterator last)　: c(first, last)
	{ make_heap( c.begin(), c.end(), comp); }
	
	bool empty() const { return c.empty(); }
	size_type size() const { return c.size(); }
	const_reference top() const { return c.front(); }
	void push( const value_type& x ){
		__STL_TRY{
			//push_back 是泛型算法，先利用底层容器的 push_back() 将新元素
			//插入末端，再重排 heap。
			c.push_back();
			push_heap( c.begin(), c.end(), comp );
		}
		__STL_UNWIND( c.clear() );
	}
	
	void pop(){
		__STL_TRY{
			//pop_heap 是泛型算法，从 heap 中取出一个元素，它并不是真正的将
			//元素弹出，而是重排 heap，然后再以底层容器的 pop_back() 取得被弹出的元素。
			pop_heap( c.begin(), c.end(), comp );
			c.pop_back();
		}
		__STL_UNWIND( c.clear() );
	}
};

 

 

priority_queue 的使用

 

top 返回到 priority_queue 顶元素的引用

const_reference top() const;

此元素将在调用 pop() 时被移除。若使用默认比较函数，则返回的元素亦为优先队列中最大的元素。

 

empty 检查底层容器是否为空

[[nodiscard]] bool empty() const;

 

size 返回底层容器中的元素数

size_type size() const;

 

push 添加给定的元素 value 到 priority_queue 中

void push( const value_type& value );
void push( value_type&& value );

(1) 等效地调用 c.push_back(value); std::push_heap(c.begin(), c.end(), comp);

(2) 等效地调用 c.push_back(std::move(value)); std::push_heap(c.begin(), c.end(), comp);

 

pop 从 priority_queue 移除堆顶元素

void pop();

等效地调用 std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); 。

 

emplace 添加新元素到 priority_queue

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

原位构造元素，即不进行移动或复制操作。以与提供给函数者准确相同的参数调用元素的构造函数。

 

swap 交换容器适配器与 other 的内容

void swap( priority_queue& other ) noexcept(/* see below */);

 

代码:

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // 用 lambda 比较元素。
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3);
 
}

输出：
9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
8 9 6 7 4 5 2 3 0 1

 

 

泛型算法 make_heap()、push_heap()、pop_heap()

make_heap()

template< class RandomIt >
constexpr void make_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void make_heap( RandomIt first, RandomIt last, Compare comp );

make_heap() 在范围 [first, last) 中构造堆。Compare有两种参数，一种是greater(生成小顶堆)，一种是less(生成大顶堆)。之后的参数含义相同，不再赘述。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
 
int main()
{
    std::cout << "Max heap:\n";
 
    std::vector<int> v { 3, 2, 4, 1, 5, 9 };
 
    std::cout << "initially, v: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    std::make_heap(v.begin(), v.end());
 
    std::cout << "after make_heap, v: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    std::pop_heap(v.begin(), v.end());
 
    std::cout << "after pop_heap, v: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    auto top = v.back();
    v.pop_back();
    std::cout << "former top element: " << top << '\n';
 
    std::cout << "after removing the former top element, v: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n' << '\n';
 
    std::cout << "Min heap:\n";
 
    std::vector<int> v1 { 3, 2, 4, 1, 5, 9 };
 
    std::cout << "initially, v1: ";
    for (auto i : v1) std::cout << i << ' ';
    std::cout << '\n';
 
    std::make_heap(v1.begin(), v1.end(), std::greater<>{});
 
    std::cout << "after make_heap, v1: ";
    for (auto i : v1) std::cout << i << ' ';
    std::cout << '\n';
 
    std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
 
    std::cout << "after pop_heap, v1: ";
    for (auto i : v1) std::cout << i << ' ';
    std::cout << '\n';
 
    auto top1 = v1.back();
    v1.pop_back();
    std::cout << "former top element: " << top1 << '\n';
 
    std::cout << "after removing the former top element, v1: ";
    for (auto i : v1) std::cout << i << ' ';
    std::cout << '\n';
}

输出：
Max heap:
initially, v: 3 2 4 1 5 9 
after make_heap, v: 9 5 4 1 2 3 
after pop_heap, v: 5 3 4 1 2 9 
former top element: 9
after removing the former top element, v: 5 3 4 1 2 
 
Min heap:
initially, v1: 3 2 4 1 5 9 
after make_heap, v1: 1 2 4 3 5 9 
after pop_heap, v1: 2 3 4 9 5 1 
former top element: 1
after removing the former top element, v1: 2 3 4 9 5

 

push_heap()

template< class RandomIt >
constexpr void push_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void push_heap( RandomIt first, RandomIt last, Compare comp );

push_heap() 插入位于位置 last-1 的元素到范围 [first, last-1) 所定义的堆中。

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
    std::vector<int> v { 3, 1, 4, 1, 5, 9 };
 
    std::make_heap(v.begin(), v.end());
 
    std::cout << "v: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    v.push_back(6);
 
    std::cout << "before push_heap: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    std::push_heap(v.begin(), v.end());
 
    std::cout << "after push_heap: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
}

输出：
v: 9 5 4 1 1 3 
before push_heap: 9 5 4 1 1 3 6 
after push_heap:  9 5 6 1 1 3 4

 

pop_heap()

template< class RandomIt >
constexpr void pop_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void pop_heap( RandomIt first, RandomIt last, Compare comp );

pop_heap()交换在位置 first 的值和在位置 last-1 的值，并令子范围 [first, last-1) 变为堆。

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
    std::vector<int> v { 3, 1, 4, 1, 5, 9 };
 
    std::make_heap(v.begin(), v.end());
 
    std::cout << "v: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    std::pop_heap(v.begin(), v.end()); // 移动最大元素到结尾
 
    std::cout << "after pop_heap: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    int largest = v.back();
    v.pop_back();  // 实际移出最大元素
    std::cout << "largest element: " << largest << '\n';
 
    std::cout << "heap without largest: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
}

输出：
v: 9 5 4 1 1 3 
after pop_heap: 5 3 4 1 1 9 
largest element: 9
heap without largest: 5 3 4 1 1

 

本文标签： 详解源码priorityqueue