Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

Напиши код на C++ Реализация класса «priority_queue». Самостоятельно реализовать…

  1. User

    Напиши код на C++ Реализация класса «priority_queue». Самостоятельно реализовать основные методы данного класса, не используя стандартный класс. Предусмотреть возможность задания приоритета с помощью внешней функции (объекта-функции).

  2. Assistant

    #include #include using namespace std;

    template<typename T, typename Compare = less> class priority_queue { private: vector data; // вектор хранения данных Compare cmp; // объект функции для сравнения элементов

    void sift_up(int i) {
        while (i > 0) { // пока не достигнут корень кучи
            int parent = (i - 1) / 2; // родитель текущего элемента
            if (cmp(data[parent], data[i])) { // если родитель меньше текущего элемента
                swap(data[parent], data[i]); // меняем их местами
                i = parent; // переходим к родителю
            }
            else break; // если родитель больше или равен текущему элементу, то куча уже упорядочена
        }
    }
    
    void sift_down(int i) {
        int left = 2 * i + 1; // левый потомок
        int right = 2 * i + 2; // правый потомок
        int largest = i; // индекс наибольшего элемента
        if (left < data.size() && cmp(data[largest], data[left])) // если левый потомок больше родителя
            largest = left;
        if (right < data.size() && cmp(data[largest], data[right])) // если правый потомок больше наибольшего элемента
            largest = right;
        if (largest != i) { // если наибольший элемент не является текущим элементом
            swap(data[i], data[largest]); // меняем их местами
            sift_down(largest); // продолжаем просеивание вниз
        }
    }
    

    public: priority_queue() {} // конструктор без параметров

    priority_queue(Compare comp) : cmp(comp) {} // конструктор с параметром функции сравнения
    
    bool empty() const { // проверка на пустоту
        return data.empty();
    }
    
    int size() const { // размер кучи
        return data.size();
    }
    
    void push(const T& value) { // добавление элемента в кучу
        data.push_back(value); // добавляем элемент в конец вектора
        sift_up(data.size() - 1); // просеиваем вверх
    }
    
    void pop() { // удаление наибольшего элемента из кучи
        if (!empty()) {
            swap(data.front(), data.back()); // меняем местами наибольший и последний элементы
            data.pop_back(); // удаляем последний элемент (ранее был наибольшим)
            sift_down(0); // просеиваем вниз
        }
    }
    
    const T& top() const { // доступ к наибольшему элементу кучи
        if (!empty()) {
            return data.front();
        }
    }
    

    };

    int main() { priority_queue pq; pq.push(30); pq.push(40); pq.push(10); pq.push(20); pq.push(50);

    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    
    cout << endl;
    return 0;
    

    }

  3. User

    Опиши каждую функцию кода выше

  4. Assistant
    1. template<typename T, typename Compare = less<T>> class priority_queue: определение шаблонного класса priority_queue с двумя параметрами-типами: T - тип элемента кучи, Compare - тип функции сравнения элементов, по умолчанию используется less<T>.

    2. private:: указание, что все последующие функции являются приватными и могут быть доступны только изнутри класса.

    3-7. vector<T> data; Compare cmp;: задание двух членов-данных класса: data - вектор содержащий элементы кучи типа T, cmp - объект функции типа Compare для сравнения элементов.

    8-20. Функция sift_up(int i): функция просеивания вверх. Ключевое замечание здесь - мы используем оператор less для сравнения элементов типа T, поэтому, если мы хотим увеличить приоритет элементов (то есть наибольшие элементы должны быть первыми, а не последними), определяем функцию сравнения < или >. Далее этот оператор используется в коде, чтобы сравнить элементы.

    21-38. Функция sift_down(int i): функция просеивания вниз.

    39-43. public:: открытая область функций доступная для использования из-за класса.

    44-48. priority_queue() {}: конструктор без параметров.

    49-53. priority_queue(Compare comp) : cmp(comp) {}: конструктор с параметром функции сравнения.

    54-59. bool empty() const { return data.empty(); }: функция проверки на пустоту.

    60-64. int size() const { return data.size(); }: функция определения количества элементов в куче.

    65-73. void push(const T& value): функция добавления элемента в кучу.

    74-85. void pop(): функция удаления элемента из кучи.

    86-91. const T& top() const: функция доступа к наибольшему элементу кучи.

    92-99. Основная программа для проверки работы priority_queue.