18

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

谁能告诉我这种优先级队列的名称，以便我知道要搜索什么，或者更好的是，为我指出一个实现？

4

5 回答 5

11

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

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

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

于 2010-05-06T15:28:53.430 回答
5

一个标准的二叉堆支持 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 min-max-heap。

于 2010-02-18T12:16:16.273 回答
2

我建议首先尝试 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);
  }
}
于 2010-02-19T15:23:48.950 回答
0

Google为您提供了许多答案，包括Java中的一个实现。

但是，这听起来像是一个家庭作业问题，所以如果是这样，我建议您先尝试自己完成这些想法，然后如果您卡在某个地方并且需要指向正确方向的指针，则可能会参考其他人的实现. 这样，您不太可能对其他程序员使用的精确编码方法产生“偏见”，并且更有可能理解为什么要包含每段代码以及它是如何工作的。有时，做类似“复制和粘贴”的释义可能有点太诱人了。

于 2010-02-18T11:43:47.400 回答
0

我正在寻找完全相同的东西！

这是我的一些想法：

  1. 由于项目的优先级不断变化，因此在检索项目之前对队列进行排序是没有意义的。
  2. 所以，我们应该忘记使用优先队列。并在检索项目时对容器进行“部分”排序。

并从以下 STL 排序算法中进行选择：分区 b。稳定分区 C. 第 n 个元素 d. 部分排序 e。partial_sort_copy f. 排序 g。稳定排序

partition、stable_partition 和 nth_element 是线性时间排序算法，应该是我们的第一选择。

但是，官方Java库中似乎没有提供这些算法。因此，我建议你使用 java.util.Collections.max/min 来做你想做的事。

于 2010-05-06T10:52:32.683 回答