gpt4 book ai didi

c++ - 为什么 std::priority_queue 对其容器的元素进行排序?

转载 作者:行者123 更新时间:2023-12-05 08:47:12 25 4
gpt4 key购买 nike

我注意到 std::priority_queue 以排序的方式存储元素。显然,以排序方式存储元素将是一个糟糕的设计选择,因为 pushpop 的时间复杂度会飙升至 O(n)。但事实证明,std::priority_queue 神奇地在线性时间内对元素进行排序。

这是我用来测试的代码。

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
#include <climits>
#include <fstream>
#include <ios>

int main() {
int size = 10'000'000;

std::random_device rd;
std::mt19937 mt{rd()};
std::uniform_int_distribution<int> uid{1, INT32_MAX};

std::vector<int> vs;
for (int i = 0; i < size; ++i) {
vs.push_back(uid(mt));
}

// Measures time taken by make_heap
std::vector<int> vs1{vs};
auto start = std::chrono::system_clock::now();
std::make_heap(vs1.begin(), vs1.end());
auto end = std::chrono::system_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Time taken by make_heap: " << diff.count() << std::endl;

// Measures time taken by priority_queue
std::vector<int> vs2{vs};
start = std::chrono::system_clock::now();
std::priority_queue<int, std::vector<int>, std::greater<int>> qs{vs2.begin(), vs2.end()};
end = std::chrono::system_clock::now();
diff = end - start;
std::cout << "Time taken by priority_queue: " << diff.count() << std::endl;

// Measures time taken by sort
std::vector<int> vs3{vs};
start = std::chrono::system_clock::now();
std::sort(vs3.begin(), vs3.end());
end = std::chrono::system_clock::now();
diff = end - start;
std::cout << "Time taken by sort: " << diff.count() << std::endl;

std::ofstream ofile;
ofile.open("priority_queue_op.txt", std::ios::out);
for (int i = 0; i < size; ++i) {
ofile << qs.top() << std::endl;
qs.pop();
}
ofile.close();

ofile.open("sort_op.txt", std::ios::out);
for (auto& v : vs3)
ofile << v << std::endl;
ofile.close();

// run `diff priority_queue_op.txt sort_op.txt`

return 0;
}
$ g++ -O3 test.cpp -o test
$ ./test
Time taken by make_heap: 0.133292
Time taken by priority_queue: 0.151002
Time taken by sort: 0.910701
$ diff priority_queue_op.txt sort_op.txt
$

从上面的输出看来,std::priority_queue 正在线性时间内对元素进行排序。

This site建议 std::priority_queue 使用标准库中的堆函数在内部管理堆。甚至源代码也证实了这一点。

Line 596 - 605

      template<typename _InputIterator>
priority_queue(_InputIterator __first, _InputIterator __last,
const _Compare& __x = _Compare(),
_Sequence&& __s = _Sequence())
: c(std::move(__s)), comp(__x)
{
__glibcxx_requires_valid_range(__first, __last);
c.insert(c.end(), __first, __last);
std::make_heap(c.begin(), c.end(), comp);
}

插入过程用于插入元素,后跟 std::make_heap 以构建堆。那么元素是如何神奇地排序的呢?即使有事情,它又是如何在线性时间内发生的?

最佳答案

So how are the elements magically sorted?

它们没有“排序”。

它们的排列方式使得应该位于 "top" 的元素在正确的位置。其他元素保证会被排序。相反,它们排列在所谓的 heap 中。 .

换句话说,一个std::priority_queue是一个经过优化的容器,可提供对逻辑上属于“顶部”的对象的快速访问,并假设其他元素在属于顶部之前不会被访问。

“其他元素不会被访问”条件允许组织比完整排序更快。

And even if there is something how is it happening in linear time?

如果您指的是插入/删除,它实际上是在对数时间内完成的。

在对数时间内,保证前面的item在正确的位置,同时保证所有其他item组成有效堆。如果数据在插入/删除之前已经是堆,这不会花很长时间。

关于c++ - 为什么 std::priority_queue 对其容器的元素进行排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68136531/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com