隨機存取優先級隊列

Question

繼續List to priority queue

我採取隨機訪問的改進priority_queue。

template <class T, class Container = std::vector<T> > 
class Heap { 
public: 
    Heap() {} 

    Heap(const Container& container) { 
     container_ = container; 
     std::make_heap(container_.begin(), container_.end()); 
    } 

    Heap<T, Container>& operator=(const Heap<T, Container>& heap) { 
     if (this != &heap) 
      container_ = heap.container_; 

     return *this; 
    } 

    void push(const T& x) { 
     container_.push_back(x); 
     std::push_heap(container_.begin(), container_.end()); 
    } 

    void pop() { 
     std::pop_heap(container_.begin(), container_.end()); 
     container_.pop_back(); 
    } 

    const T& top() { 
     return container_.front(); 
    } 

    const Container& getContainer() const { 
     return container_; 
    } 

    T& operator[](size_t n) { 
     return container_[n]; 
    } 

    typename Container::const_iterator begin() const { 
     return container_.begin(); 
    } 

    typename Container::const_iterator end() const { 
     return container_.end(); 
    } 

    size_t size() const { 
     return container_.size(); 
    } 

    T& base() { 
     return container_.back(); 
    } 

    Container::iterator erase(Container::iterator position) { 
     return container_.erase(position); 
    } 

private: 
    Container container_; 
}; 

我採取了正確的方法嗎？

• 修復了一元構造函數。
• 改進後的代碼。

Answer 1

不看，偉大的對我說：

• 一元的構造應該由const引用取的說法。
• 賦值運算符不檢查自賦值。
• getContainer()方法顯示界面缺乏清晰度 - 爲什麼您只需公開實現細節？
• 最重要的是：爲什麼你想要一個「隨機存取優先級隊列」？

Answer 2

您的pop（）方法可能會違反堆排序。使用pop_heap（）而不是pop_back（）。我現在似乎無法找到任何其他錯誤。

您可以輕鬆地通過推入隨機整數並逐個pop（）來測試這種實現。你應該按排序順序將它們取回。這被稱爲堆排序。

建議：

• 而不是一個裁判返回容器，你可以實現一個常量迭代此類。

• 請注意，您不應該更改隨機訪問的元素的鍵，因爲它可能會破壞堆結構。如果你需要這樣的功能，你應該實現一個change_key函數，它可以安全地改變密鑰並保持堆的順序。