优先队列堆化

Question

有没有办法用O(N) 复杂度的某些元素来初始化优先级队列？可能使用 heapify 算法。

我搜索了那个问题，但找不到解决方案。另外，我知道 make_heap()，但这是另一回事，与优先级队列无关。

Answer 1

Is there any way to initialize priority queue with some elements in O(N) complexity?

是； std::priority_queue<...> 有一个构造函数。 https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue 给出了这个例子：

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue<int> c3(std::less<int>(), vec);

将 c3 初始化为包含 vec.

元素的优先级队列（最大堆）

编辑回复评论：

what would be the compare function to heapify into a min-heap? I know there is a function called greater<int>(); but it doesn't seem to work for some reason on c++14

所以，std::less 有点特殊，所以用它作为例子可能会产生误导。 std::priority_queue class 模板实际上采用三个类型参数：元素类型、容器类型和比较器类型。在上面的示例中，它们分别是 int、std::vector<int> 和 std::less<int>。我们不必在上面的例子中显式地写容器类型和比较器类型的原因是这两个类型参数有默认值，而在上面的例子中，默认值正是我们想要的。

要改用 std::greater<int>，与上面的等价的是：

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue<int, std::vector<int>, std::greater<int>> c3(std::greater<int>(), vec);

但是如果您使用的是 C++17 或更高版本，则可以完全删除模板参数列表并让编译器推断它：

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue c3(std::greater<int>(), vec);

（注意：这不是与写作 std::priority_queue<int> 相同 — 包括任何模板参数列表都会告诉编译器您希望它使用默认值未指定的参数，而不是使用模板参数推导。）

如果您坚持使用 C++14 并且想避免必须编写 std::greater<int>() 两次，那么 slight 改进是使用其中一个构造函数不需要比较对象：

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue<int, std::vector<int>, std::greater<int>> c3(vec.cbegin(), vec.cend());

但是使用 C++17 或更高版本肯定会使它更干净。 :-)

优先队列堆化

Priority Queue Heapify

c++

algorithm

heap

stl

priority-queue