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

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

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

来源

2010-02-18 sean

见http://stackoverflow.com/questions/927631/is-there-a-heap-class-in-c-that-supports-changing-the-priority-of-elements-othe和http：// stackoverflow.com/questions/450180/a-priority-queue-which-allows-efficient-priority-update – 2010-02-18 15:40:51

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

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

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

来源

2010-02-19 15:23:48

谢谢Matthieu，我想过使用这种方法，但由于更新的频率，它不足以满足我的需求。我最终使用了一个实现，它包含一个将项目映射到其队列索引的字典，然后在队列UpdatePosition（Item item）上有一个方法，它查找项目索引，然后将其引入新的位置。队列然后有一个事件，这些项目进行注册，以便它们在优先级改变时通知队列。这似乎运作良好。 – sean 2010-02-20 12:13:56

Google has a number of answers给你，包括执行one in Java。

但是，这听起来像是一个家庭作业问题，所以如果是这样，我会建议先尝试自己的想法，然后可能引用其他人的实现，如果你卡在某处并需要一个指针在正确的方向。这样，你就不太可能对另一个程序员使用的精确编码方法产生“偏见”，并且更可能理解为什么要包含每段代码以及它的工作原理。有时候，复制和粘贴相当于“复制和粘贴”，这可能有点太诱人。

来源

2010-02-18 11:43:47 Amber

感谢Dav，但这是一个标准的优先级队列。如果我将一个项目添加到队列中并且它的优先级发生了更改（队列外），则队列的顺序可能不正确。换句话说，一个标准的优先级队列只在将它们添加到队列中时才对它们进行排序，而不是稍后。我需要实现一个更新为队列更新优先级的队列。 P.S.这不是一个家庭作业问题，我需要将它作为一些仿真软件的一部分来实现。我对如何实现它有一些想法，但想知道是否有更好的方法来实现它。 – sean 2010-02-18 11:55:02

啊。好的。在这种情况下，我建议寻找Dijkstra算法的示例实现，该算法（如果以最有效的形式实现）需要可重新配置的优先级队列，因此应该可能具有您要查找的内容。 – Amber 2010-02-18 23:08:05

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

来源

2010-02-18 12:16:16 Martin

如果您首先需要搜索您希望增加的元素，我看不出二进制堆如何有效地支持增加键。由于堆中没有排序，因此需要线性时间来查找元素。 – wcochran 2012-11-08 04:27:18

您必须对元素进行引用才能使增加键和减少键效率更高。这是用Boost.Heap C++库中的句柄实现的http://www.boost.org/doc/libs/1_55_0/doc/html/heap/concepts.html#heap.concepts.mutability – lazd 2014-07-09 00:37:54

我找只完全一样的东西！

这里是我的一些想法：

由于项目的优先级不断变化，这是毫无意义的检索项目之前，队列排序。
所以，我们应该忘记使用优先级队列。并在检索项目时“部分”分类容器。

，并从以下STL排序算法：一个。分区 b。 stable_partition c。 nth_element d。 e。 partial_sort_copy f。 g。分类 g。stable_sort

分区，stable_partition和nth_element是线性时间的排序算法，这应该是我们的第一个选择。

，但似乎没有在正式的Java库提供的算法。因此，我会建议你使用java.util.Collections.max/min来做你想做的事情。

来源

2010-05-06 10:52:32 Henry

优先队列如此使用的二进制堆数据结构作为他人提出，其通常使用的阵列表示，但也可以使用二进制树通常被实现。实际上并不难增加或减少堆中元素的优先级。如果您知道在下一个元素从队列中弹出之前您正在更改许多元素的优先级，那么可以暂时关闭动态重新排序，将所有元素插入到堆的末尾，然后重新排序整个堆（成本O（n））就在元素需要弹出之前。堆的重要之处在于它只需要将数组放入堆序列中，而将O（n log n）排序为O（n）。

我已经与动态优先级的大型项目中使用这种方法成功。

这是我实现的一个参数priority queue implementation in the Curl programming language。

来源

2010-05-06 15:28:53

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

回答

相关问题