C++向量插入元素

Question

我正在尝试使用存储每个元素的向量构建优先级队列。首先，我想将元素以其优先级插入向量。我不确定是否有可能，如果没有，有人可以给我另一个解决方案吗？这是我的代码：

template <typename E>
class PriorityQueue {
private:
    std::vector<E> elements;
    E value;
    int pr; 
public:
  PriorityQueue() {}
  void insert(int priority, E element) {

  }   
};

Answer 1

以下是创建具有 vector 优先级的元素的方法：

 struct PriElement
    {
        int data;
        int pri;
        bool operator < ( const PriElement & other ) const
        {
            return pri < other.pri;
        }
    };
    vector<PriElement> _vector;

但是，真正的问题是保持向量按优先级排序。

下面是一个显示气泡方法的朴素实现：

class PriorityQueue{
public:
    void insert( int data, int pri )
    {
        _vector.push_back(PriElement(data,pri));
        int index = _vector.size() -1;
        while ( ( index > 0 )&& (_vector[index] < _vector[index-1] ) )
        {
            swap(_vector[index],_vector[index-1]);
            index--;
        }
    }
private:
    vector<PriElement> _vector;
};

如前所述，对于任何实际实现，请使用priority_queue。

Answer 2

执行此操作的标准算法(参见算法简介第6章(如下：

1. 推动项目时，将其插入矢量的末尾，然后将其"冒泡"到正确的位置。

2. 弹出最小项目时，将第一个项目(位置 0(替换为末尾的项目，然后将其"冒泡"到正确的位置。

可以证明这可以通过(摊销的(对数时间来完成(摊销是由于向量可能自身翻倍(。

但是，没有必要自己实现这一点，因为标准库包含std::priority_queue它是一个使用 std::vector 作为其默认序列容器的容器适配器。例如，如果您定义

std::priority_queue<int> q;

然后q将是适应向量的优先级队列。