具有动态项目优先级的优先级队列

小编典典

具有动态项目优先级的优先级队列

algorithm

我需要实现一个优先级队列，该队列中的项的优先级可以更改，并且队列会自行调整，以便始终以正确的顺序删除项。我对如何实现此方法有一些想法，但是我确信这是一个非常常见的数据结构，因此我希望可以由比我聪明的人作为基础来使用实现。

谁能告诉我这种类型的优先级队列的名称，这样我就知道要搜索什么，或者甚至更好地为我指出一个实现？

阅读 258

2020-07-28

共1个答案

小编典典

我建议先尝试采用直接面对的方法来更新优先级：

从队列中删除项目
以新的优先级重新插入

在C
++中，可以使用来完成此操作std::multi_map，重要的是，对象必须记住它在结构中的存储位置，以便能够有效地删除自身。对于重新插入，这很困难，因为您无法假设自己对优先级一无所知。

class Item;

typedef std::multi_map<int, Item*> priority_queue;

class Item
{
public:
  void add(priority_queue& queue);
  void remove();

  int getPriority() const;
  void setPriority(int priority);

  std::string& accessData();
  const std::string& getData() const;

private:
  int mPriority;
  std::string mData;

  priority_queue* mQueue;
  priority_queue::iterator mIterator;
};

void Item::add(priority_queue& queue)
{
  mQueue = &queue;
  mIterator = queue.insert(std::make_pair(mPriority,this));
}

void Item::remove()
{
  mQueue.erase(mIterator);
  mQueue = 0;
  mIterator = priority_queue::iterator();
}

void Item::setPriority(int priority)
{
  mPriority = priority;
  if (mQueue)
  {
    priority_queue& queue = *mQueue;
    this->remove();
    this->add(queue);
  }
}

2020-07-28