具有動態項目優先級的優先級隊列

我需要實現優先級隊列，其中隊列中項目的優先級可以更改，並且隊列自行調整，以便項目始終以正確的順序刪除。我對如何實現這一點有一些想法，但我確定這是一個相當常見的數據結構，所以我希望我可以使用比我更聰明的人作爲基礎的實現。具有動態項目優先級的優先級隊列

任何人都可以告訴我這種類型的優先級隊列的名稱，所以我知道要搜索什麼，甚至更好，指向我的實現？

來源

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

具有動態項目優先級的優先級隊列

回答

相關問題