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

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

class BinaryHeap {
 private:
  std::vector<int> data;

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

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

      if (left < size && data[left] > data[largest]) largest = left;
      if (right < size && data[right] > data[largest]) largest = right;

      if (largest == index) break;

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

 public:
  BinaryHeap() = default;

  BinaryHeap(const std::vector<int>& arr) : data(arr) {
    int n = data.size();
    for (int i = n / 2 - 1; i >= 0; --i) {
      siftDown(i);
    }
  }

  int get_max() const {
    if (data.empty()) throw std::runtime_error("Heap is empty");
    return data[0];
  }

  int extract_max() {
    if (data.empty()) throw std::runtime_error("Heap is empty");

    int maxVal = data[0];
    data[0] = data.back();
    data.pop_back();

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

    return maxVal;
  }

  void insert(int value) {
    data.push_back(value);
    siftUp(data.size() - 1);
  }

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

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

  void print() const {
    for (int val : data) {
      std::cout << val << " ";
    }
    std::cout << std::endl;
  }
};

int main() {
  BinaryHeap heap1;
  heap1.insert(10);
  heap1.insert(5);
  heap1.insert(20);
  heap1.insert(15);
  heap1.insert(30);
  heap1.insert(25);

  std::cout << "Куча после вставки элементов: ";
  heap1.print();
  std::cout << "Максимальный элемент (get_max): " << heap1.get_max()
            << std::endl;

  while (!heap1.empty()) {
    std::cout << "Извлечен: " << heap1.extract_max()
              << ", осталось: " << heap1.size() << std::endl;
  }

  std::vector<int> arr = {15, 5, 20, 1, 17, 10, 25, 8, 12};
  std::cout << "Исходный массив: ";
  for (int v : arr) std::cout << v << " ";
  std::cout << std::endl;

  BinaryHeap heap2(arr);
  std::cout << "Построенная куча: ";
  heap2.print();
  std::cout << "Максимум: " << heap2.get_max() << std::endl;

  heap2.insert(28);
  std::cout << "После вставки 28: ";
  heap2.print();
  std::cout << "Новый максимум: " << heap2.get_max() << std::endl;

  std::cout << "Элементы в порядке убывания: ";
  while (!heap2.empty()) {
    std::cout << heap2.extract_max() << " ";
  }
  std::cout << std::endl;

  return 0;
}