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

Question

我需要实现一个优先级队列,其中队列中项目的优先级可以更改,队列自行调整,以便始终以正确的顺序删除项目.我有一些关于如何实现这一点的想法,但我确信这是一个非常常见的数据结构,所以我希望我可以使用比我更聪明的人作为基础的实现.

任何人都可以告诉我这种类型的优先级队列的名称,所以我知道要搜索什么,或者更好的是,我指向一个实现？

Answer 1

诸如此类的优先级队列通常使用二进制堆数据结构来实现,如同其他人建议的那样,其通常使用数组来表示,但也可以使用二叉树.实际上,增加或减少堆中元素的优先级并不困难.如果您知道在从队列中弹出下一个元素之前更改了许多元素的优先级,则可以暂时关闭动态重新排序,在堆的末尾插入所有元素,然后重新排序整个堆(需要付出代价)在元素需要弹出之前的O(n)).关于堆的重要一点是,将数组放入堆顺序只需要O(n),而对它进行排序只需要O(n log n).

我已经在具有动态优先级的大型项目中成功使用了这种方法.

这是我在Curl编程语言中实现的参数化优先级队列实现.

Answer 2

标准二进制堆支持5个操作(以下示例假设最大堆):

* find-max: return the maximum node of the heap
* delete-max: removing the root node of the heap
* increase-key: updating a key within the heap
* insert: adding a new key to the heap
* merge: joining two heaps to form a valid new heap containing all the elements of both.

如您所见,在最大堆中,您可以增加任意键.在最小堆中,您可以减少任意键.不幸的是,你不能以两种方式改变密钥,但这样做会不会？如果您需要以两种方式更改密钥,那么您可能需要考虑使用aa -max-heap.

Answer 3

我建议首先尝试使用 head-in 方法来更新优先级：

• 从队列中删除该项目
• 使用新的优先级重新插入它

在 C++ 中，这可以使用 a 来完成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);
  }
}