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

Question

我需要实现一个优先级队列，在这个队列中，项的优先级可以改变，队列会自动调整，以便项始终以正确的顺序删除。我对如何实现这一点有一些想法，但我确信这是一个相当常见的数据结构，所以我希望我可以使用比我聪明的人的实现作为基础。

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

Answer 1

我建议首先尝试正面方法，以更新优先级：

使用新的priority从queue

• re-insert it中删除项目

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

Answer 2

像这样的优先级队列通常使用其他人建议的二进制堆数据结构实现，该结构通常使用数组表示，但也可以使用二叉树表示。实际上，增加或降低堆中元素的优先级并不难。如果您知道在从队列中弹出下一个元素之前更改了许多元素的优先级，您可以暂时关闭动态重新排序，在堆的末尾插入所有元素，然后在需要弹出元素之前对整个堆进行重新排序(成本为O(n))。堆的重要之处在于，将数组放入堆的顺序只需要O(n)，而对数组进行排序只需要O(n log n)。

我在一个具有动态优先级的大型项目中成功地使用了这种方法。

下面是我的参数化priority queue implementation in the Curl programming language的实现。

Answer 3

一个标准的二进制堆支持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.

正如你所看到的，在最大堆中，你可以增加一个任意键。在最小堆中，你可以减少一个任意键。不幸的是，您不能同时使用这两种方式更改密钥，但这样做可以吗？如果您需要以两种方式更改密钥，那么您可能需要考虑使用min-max-heap。