與數據結構網絡堆等效功率和映射

Question

我想設計元件的容器C E.

E具有2個屬性（優先權，名稱），在容器的所有元素具有唯一「姓名」

我儘可能有效地支持對此容器C的後續操作。

1. 插入件： - 插入部件1（NAME1，優先級爲1）到容器： C.insert（元件（NAME1，優先級爲1））
2. 更新： - 與名稱= NAME1作爲priorityNew1元件的更新優先級： C [NAME1] = priorityNew1
3. 刪除：用名稱 - 刪除該元素= NAME1：C.delete（NAME1）
4. 得到和具有最高優先級刪除元素：C.pop（）
5. 獲取具有最高優先級的元素：C.peek（）

基本上我想要一個地圖和堆的組合。映射元素的「名稱」，並堆上元素的「優先級」。 最理想的情況是我希望每個操作都是O（1）。 否則，插入，更新，刪除爲O（log N），彈出並查看O（1）也很好。

我能想到以下兩種方法

1）使用元素的哈希表，哈希的名字。 所以插入更新刪除是O（1） pop和peek是O（N），我們搜索整個容器以獲得最高優先級。

2）使用具有兩列「名稱」和「優先級」的表'元素'的SQLite。 運行時間將基於SQLite實現。

我很想知道更多關於這個問題的想法，我正面臨一個與此相關的現實世界問題。 感謝您的輸入。

Answer 1

我不知道Boost是否會爲你工作，但我會檢查Boost Mutli索引。 http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html

您可以保持索引的優先級，以便您快速獲取並插入元素。我已經同樣使用增強多指標進行MRU/LRU情況。

#include <iostream> 
#include <string> 
#include <algorithm> 

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/sequenced_index.hpp> 
#include <boost/multi_index/identity.hpp> 
#include <boost/multi_index/member.hpp> 
#include <boost/optional.hpp> 

struct bypriority{}; 
struct byseq{}; 

struct MyElement{ 
    typedef int priority_type; 
    typedef std::string name_type; 

    name_type name; 
    priority_type priority; 

    MyElement(const name_type& name, const priority_type& priority):name(name),priority(priority){}; 
}; 

std::ostream& operator<<(std::ostream& os, const MyElement& e){ 
    os << "Name: " << e.name << " Priority: " << e.priority; 
    return os; 
} 

using namespace boost; 
using namespace boost::multi_index; 

template<typename Element> 
struct Container{ 
    typedef multi_index_container< 
     Element, 
     indexed_by< 
      //sequenced 
      sequenced<tag<byseq> >, 
      //ordered by priority 
      ordered_non_unique<tag<bypriority>,member<Element,typename Element::priority_type,&Element::priority>, std::greater<typename Element::priority_type> > 
     > 
    > Elements; 


    void insert(const Element& e){ 
     typename Elements::template index<byseq>::type& list_view = elements.get<byseq>(); 
     list_view.push_back(e); 
    } 

    boost::optional<Element> peek() const{ 
     boost::optional<Element> res; 
     typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin(); 
     if(it != elements.get<bypriority>().end()){ 
      res.reset(*it); 
     } 
     return res; 
    } 

    boost::optional<Element> pop() { 
     boost::optional<Element> res; 
     typename Elements::template index<bypriority>::type& priority_index = elements.get<bypriority>(); 
     typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin(); 
     if(it != elements.get<bypriority>().end()){ 
      res.reset(*it); 
      priority_index.erase(it); 
     } 

     return res; 
    } 

    void print_in_order(std::ostream& os) const{ 
     typedef typename Elements::template index<byseq>::type elements_by_sequence; 
     for(typename elements_by_sequence::iterator it = elements.get<0>().begin(); it != elements.get<0>().end(); it++){ 
      os << *it << std::endl; 
     } 
    } 

    protected: 
    Elements elements; 
}; 



using namespace std; 
int main(int argc, char *argv[]) { 

    Container<MyElement> c; 

    c.insert(MyElement("Bob",10)); 
    c.insert(MyElement("Alice",100)); 
    c.insert(MyElement("Fred",20)); 


    c.print_in_order(std::cout); 

    cout << endl << "Highest Priority is " << endl << *c.peek() << endl; 

    boost::optional<MyElement> alice = c.pop(); 
    if(alice){ 
     cout << "Popped results are " << *alice << endl; 
    } 


    cout << endl << "Now the contents are" << endl; 
    c.print_in_order(std::cout); 

} 

將輸出：

Name: Bob Priority: 10 
Name: Alice Priority: 100 
Name: Fred Priority: 20 

Highest Priority is 
Name: Alice Priority: 100 
Popped results are Name: Alice Priority: 100 

Now the contents are 
Name: Bob Priority: 10 
Name: Fred Priority: 20 

Answer 2

如果O(logN)每個操作是可以接受的，顯然boost::bimap就足夠了。這工作像一個雙面std::map。你可以通過維護兩個std::map幾乎相同或編寫自己的包裝（但你爲什麼？）。具有自我平衡功能的二分查找樹具有O(logN)，用於最少的檢索，效率略低於堆。

如果效率真的很重要，您應該實現自己的容器堆和散列圖。然後，在堆中交換時，將映射從name維護到哈希映射中的堆數組中。這爲O(1)提供插入，刪除，重新分配優先級O(logN)和最小/最大優先級元素。 （這不是小菜一碟，但並不乏味）