Direktzugriffsprioritätswarteschlange

Question

Liste Prioritätswarteschlange

Ich bin ein verbessertes priority_queue mit wahlfreiem Zugriff zu implementieren.

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_;
};

Bin ich den richtigen Weg zu nehmen?

• Fixed der unäre Konstruktor.
• Verbesserte Code.

Answer 1

sieht das toll, mich nicht an:

• Der unäre Konstruktor sollte Argument konstante Referenz nehmen.
• Der Zuweisungsoperator überprüft nicht für die Selbstzuordnung.
• Die getContainer() Methode zeigt einen Mangel an Klarheit in der Schnittstelle - warum sollte man einfach die Umsetzung aussetzen Detail wie die
• Am wichtigsten ist: warum wollen Sie eine „random access Prioritätswarteschlange“

Answer 2

Ihr pop () -Methode kann die Heap-Ordnung verletzen. Verwenden Sie pop_heap () anstelle von pop_back (). Ich kann nicht scheinen im Augenblick andere Fehler zu finden.

Sie können ganz einfach testen, eine solche Implementierung durch in einer zufälligen ganzen Zahlen drücken und Pop (), um sie eins nach dem anderen. Sie sollten sie zurück in sortierter Reihenfolge bekommen. Dies ist bekannt als die Stapelsortier.

Vorschläge:

• Statt einen ref an den Behälter zurückkehren Sie könnten eine const iterator zu dieser Klasse implementieren.

• Beachten Sie, dass Sie nicht den Schlüssel des zufällig zugegriffen Elements ändern sollte, weil es die Heap-Struktur zerstören. Wenn Sie diese Funktionalität benötigen, sollten Sie eine change_key Funktion implementieren, die den Schlüssel sicher ändern würde und halten die Heap-Bestellung.