动态项的优先级优先级队列 [英] Priority queue with dynamic item priorities

问题描述

我需要实现一个优先队列，其中在队列中的项目的优先级可以改变和队列自我调整，以便将项目以正确的顺序总是除去。我有我如何能实现这个的一些想法，但我敢肯定，这是一个相当常见的数据结构，所以我希望我可以一个人比我聪明的位置使用一个实现。

I need to implement a priority queue where the priority of an item in the queue can change and the queue adjusts itself so that items are always removed in the correct order. I have some ideas of how I could implement this but I'm sure this is quite a common data structure so I'm hoping I can use an implementation by someone smarter than me as a base.

谁能告诉我这种类型的优先级队列的名字，所以我知道该怎么寻找，或者甚至更好，指向我一个实现？

Can anyone tell me the name of this type of priority queue so I know what to search for or, even better, point me to an implementation?

推荐答案

我首先建议尝试头的方式，来更新优先级：

I would suggest first trying the head-in approach, to update a priority:

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

在C ++中，这可以用做了的std :: multi_map ，重要的是该对象必须记住它存储在结构，能够有效地删除自己。对于重新插入，这是困难的，因为你不能presume你了解的重点事情。

In C++, this could be done using a std::multi_map, the important thing is that the object must remember where it is stored in the structure to be able to delete itself efficiently. For re-insert, it's difficult since you cannot presume you know anything about the priorities.

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);
  }
}

这篇关于动态项的优先级优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！