work4/work_4.1/task7.cpp - develop - novd7/algirithms_sem2

work4/work_4.1/task7.cpp
118 строк3 KB
Новиков Владимир
Рабочая тетрадь 4.1
30 май 2026, 12:57
30 май 2026, 12:57043180e
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

struct Task {
  std::string name;
  int priority;

  Task(const std::string& n, int p) : name(n), priority(p) {}
};

class PriorityQueueHeap {
 private:
  std::vector<Task> heap;

  void siftUp(int index) {
    while (index > 0) {
      int parent = (index - 1) / 2;
      if (heap[index].priority <= heap[parent].priority) break;
      std::swap(heap[index], heap[parent]);
      index = parent;
    }
  }

  void siftDown(int index) {
    int size = heap.size();
    while (true) {
      int left = 2 * index + 1;
      int right = 2 * index + 2;
      int largest = index;

      if (left < size && heap[left].priority > heap[largest].priority)
        largest = left;
      if (right < size && heap[right].priority > heap[largest].priority)
        largest = right;

      if (largest == index) break;

      std::swap(heap[index], heap[largest]);
      index = largest;
    }
  }

 public:
  void addTask(const std::string& name, int priority) {
    heap.push_back(Task(name, priority));
    siftUp(heap.size() - 1);
    std::cout << "Добавлена задача: " << name << ", приоритет=" << priority
              << std::endl;
  }

  Task extractMax() {
    if (heap.empty()) throw std::runtime_error("No tasks");

    Task maxTask = heap[0];
    heap[0] = heap.back();
    heap.pop_back();

    if (!heap.empty()) siftDown(0);

    return maxTask;
  }

  Task peekMax() const {
    if (heap.empty()) throw std::runtime_error("No tasks");
    return heap[0];
  }

  void editTask(int index, const std::string& newName, int newPriority) {
    if (index < 0 || index >= static_cast<int>(heap.size()))
      throw std::out_of_range("Invalid index");

    int oldPriority = heap[index].priority;
    heap[index].name = newName;
    heap[index].priority = newPriority;

    if (newPriority > oldPriority) {
      siftUp(index);
    } else if (newPriority < oldPriority) {
      siftDown(index);
    }
  }

  bool empty() const { return heap.empty(); }

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

  void printAll() const {
    std::vector<Task> temp = heap;
    std::make_heap(temp.begin(), temp.end(), [](const Task& a, const Task& b) {
      return a.priority < b.priority;
    });

    std::cout << "\nТекущие задачи:" << std::endl;
    for (const auto& task : temp) {
      std::cout << task.name << ", приоритет=" << task.priority << std::endl;
    }
  }
};

int main() {
  PriorityQueueHeap todo;

  todo.addTask("Сдать лабораторную", 5);
  todo.addTask("Подготовиться к экзамену", 10);
  todo.addTask("Прочитать главу", 3);

  todo.printAll();

  std::cout << "\nВыполняется: " << todo.extractMax().name << std::endl;
  std::cout << "Следующая: " << todo.peekMax().name << std::endl;

  todo.printAll();

  return 0;
}