Напиши код на C++ Реализация класса «priority_queue». Самостоятельно реализовать…
- User
Напиши код на C++ Реализация класса «priority_queue». Самостоятельно реализовать основные методы данного класса, не используя стандартный класс. Предусмотреть возможность задания приоритета с помощью внешней функции (объекта-функции).
- 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;}
- User
Опиши каждую функцию кода выше
- Assistant
-
template<typename T, typename Compare = less<T>> class priority_queue: определение шаблонного классаpriority_queueс двумя параметрами-типами:T- тип элемента кучи,Compare- тип функции сравнения элементов, по умолчанию используетсяless<T>. -
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. -