可以使用简单队列制作优先级队列吗

Question

优先队列只是一个排序队列吗？可以通过创建一个简单的队列然后对其进行排序来实现吗？ https://www.quora.com/What-is-the-difference-between-a-priority-queue-and-a-queue?share=1 我发现了这个 link 并且它声明可以通过 在插入时重新安排队列来创建优先级队列，然后放入最近插入的对象在适当的优先位置。我想确定一下，因为我的一些同行说这是不可能的，但是如果我们创建一个遵循优先级的队列，它不会使队列成为优先级队列吗？

Answer 1

差不多。

您不能 "sort" 标准队列，因为它没有随机访问。 std::priority_queue 通常由向量支持。

它只是为您完成 "automatic sorting"，仅此而已。你实际上不会重新排序整个事情（这会做很多毫无意义的比较）：你会做一个 lower/upper 绑定搜索来插入你的新元素的位置。删除可以类似地专门化，因为你知道元素是排序的，所以可以进行二进制搜索。

但最终结果是一个行为很像队列的东西，是的。

Answer 2

A priority queue 是一个抽象数据结构，具有一些必需的操作：

检查是否空虚(is_empty);
按 "priority" (insert);
查找并删除具有最高优先级 (pop) 的元素。

有很多方法可以实现这一点，但您通常会寻找 pop 和 insert 的 O(log n)（摊销）复杂度。

一个queue是一个抽象的数据结构，你在后面插入，在前面删除，所以它不能用来实现优先级队列（没有"ordering"，除了先进先出）。

实现优先级队列最简单的方法通常是使用标准库中定义的 binary heap. A minimalist C++ implementation using a std::vector<int> as a backend and the heap operations 可以是：

#include <algorithm>
#include <vector>

using priority_queue = std::vector<int>;

bool is_empty(priority_queue const& q) { return q.empty(); }

void insert(priority_queue &q, int value) { 
    q.push_back(value);
    std::push_heap(std::begin(q), std::end(q));
}

int pop(priority_queue &q) {
    std::pop_heap(std::begin(q), std::end(q));
    const int value = q.back();
    q.pop_back();
    return value;
}

insert 和 pop 的（摊销）O(log n) 复杂度。

可以使用简单队列制作优先级队列吗

Can priority queue be made by using simple queues

c++

queue

priority-queue

data-structures